[알고리즘] 다이나믹 프로그래밍(DP)

분할 정복으로 문제를 풀지 않고 구한 문제들을 기록해가며 푸는 방식

// 일반적인 피보나치 수열
#include<iostream>
using namespace std;
 
int fibonacci(int a) {
    if (a == 1) return 1;
    if (a == 2) return 1;
 
    return fibonacci(a - 1) + fibonacci(a - 2);
}
int main() {
    cout<<fibonacci(10);
}
 
 

피보나치 수열을 분할 정복 방식으로 풀게 되면, 수가 커질수록 기하급수적인 호출이 일어나게 된다. 

fibonacci(10) 을 구하려면 fibonacci(9) + fibonacci(8) 인데 여기서 또 fibonacci(9)가 fibonacci(8)+ fibonacci(7)인것 처럼 구한 식을 다시 구하게 되는 불필요한 연산이 일어난다.

 

이 문제를 다이나믹 프로그래밍 기법으로 풀게되면 

// DP를 활용한 피보나치 수열
#include<iostream>
using namespace std;
 
int tmp[1000] = { 0 };
 
int fibonacci(int a) {
    if (a == 1) return 1;
    if (a == 2) return 1;
    if (tmp[a] != 0) return tmp[a];
    return tmp[a] = fibonacci(a - 1) + fibonacci(a - 2);
}
int main() {
    cout<<fibonacci(40);
}
 
 

계산한 값을 배열에 따로 저장해줌으로써 불필요한 계산을 줄일수 있다.