c++) 피보나치 - 동적 계획법(Fibonacci - Dynamic Programming)

재귀를 배우기 시작하면, 모두들 해보셨을 예제로 피보나치 수열이 있죠.

대부분 수업시간에서는 그렇게 크지 않은 숫자를 예제로 돌렸을 것이라 생각합니다.

근데 숫자가 커지게 된다면, 재귀를 무지막지하게 해서 TLE (Time limited exceeded)가 생기겠죠?

그렇기 때문에 동적 계획법을 통하여 코딩을 합니다.

개요

- 배열 or 리스트를 생성하여 이전 피보나치 값들을 저장합니다.

- 이 데이터 구조를 이용하여 재귀의 숫자를 획기적으로 줄여봅니다.

==> 이러한 기법을 Memoization 기법이라 합니다. 

(DP의 핵심 기술)

코드

#include <iostream>

using namespace std;

#define SIZE 1000

long long save[SIZE] = { 0, 1, 1, };

long long fibo(int num) {
	if (save[num]) return save[num];
	else return save[num] = fibo(num - 2) + fibo(num - 1);
}

int main() {

	int n;

	cin >> n;
	cout << "fibonacci result : " << fibo(n) << endl;

	return 0;
}

성능

- 기존 재귀 방법 : O(2^n) --> 매번 두가지 선택지가 늘어나기 때문.

- Memoization 방법 : O(n)

실행 화면은 생략하겠습니다 ^^