1. DP : 피보나치 수열

피보나치 수열을 Recursive로 구현해보면, 중복되는 계산을 너무 많이 하게된다. 하나의 함수는 두개의 함수를 호출하므로 대충 O() 정도의 시간복잡도를 지닌다.

//Recursive Function int fibonacci_rcs(int n) { if (n == 0) { return 0; } if (n==1) { return 1; } return fibonacci_rcs(n - 2) + fibonacci_rcs(n - 1); }

이러한 재귀적인 중복계산으로 시간을 낭비하는 일을 줄이기 위해 DP를 사용하여 코드를 짤 수 있다. 아래는 DP를 이용한 코드다. 벡터를 이용해 각 함수의 결과값을 저장해놓고 필요할 때, 또 다시 계산하지 않고 바로 참조하여 값을 불러온다. 이것을 메모이제이션이라고 한다.

vector<int> dp; int fibonacci_dp(int n) { if (n == 0) return 0; if (n == 1) return 1; //이미 값을 계산한 적이 있다면 그 값을 참조하여 바로 리턴 if (dp[n] != -1) return dp[n]; //아니라면 계산해서 dp 리스트에 새로 넣어줌 dp[n] = fibonacci_dp(n - 2) + fibonacci_dp(n - 1); return dp[n]; } int main() { int N = 0; cout << "input number: "; cin >> N; //Recursive function //cout << fibonacci_rcs(N); //dp dp.resize(N + 1, -1); cout << fibonacci_dp(N); return 0; }

fibonacci_dp(5)라면, dp[2]부터 값이 채워지기 시작한다. dp[3]은 dp[2]값과 1이 리턴되서 채워지고, 그 후 부터는 fibonacci(3)을 계산하지 않고 dp[3]을 참조하여 값을 구할 수 있다. 이런식으로 계산량을 줄여 알고리즘을 짤 수 있다.

백준 관련문제 :  2747번 문제: 피보나치 수,  2748번 문제: 피보나치 수 2, 2749번 문제: 피보나치 수 3 ,  11444번 문제: 피보나치 수 6

2748번 문제: 피보나치 수 2 의 경우, 범위 때문에 long long 타입을 사용해야한다.