[C++/알고리즘][다이나믹 프로그래밍(동적계획법)-DP]

이번 시간에는 다이내믹 프로그래밍을 알아보도록 하겠습니다.

다이나믹 프로그래밍은 재귀적으로 문제를 해결할 때 불필요하게 같은 연산을 하는 것을 없애고자 만들어진 알고리즘 기법입니다.

대표적인 예로 피보나치 수열을 예로 들어서 설명하겠습니다.

피보나치수열

피보나치수열은 0,1로 시작하고 그다음 피 보나 치수는 앞에 두 수를 더한 값이 됩니다.

Ex) 0,1,1,2,3,5,8,13,21,34,55,89....

피보나치수열을 재귀적으로 구현했을 경우 코드는 다음과 같습니다.

코드

#include <iostream>
using namespace std;
int fibo(int n){
    if(n == 1){return 1;}
    else if(n == 0){return 0;}
    return (fibo(n-1)+fibo(n-2));
}
int main(void){
    int N = 6;
    cout << fibo(N);
    cout << "\n";
}

피보나치 수열을 재귀적으로 구현했을 때 피보나치 수 6을 구하는 것을 그래프로 표현해 봤습니다.

똑같은 피 보나 치수를 호출하는 것이 상당히 많습니다. fibo 2는 5번이나 호출이 되는 것을 알 수 있습니다.

이미 fibo2 나 fibo3과 같은 이미 방문하여 값을 알고 있는데 다시 방문할 필요가 있을까요? 

그래서 고안된 방법이 다이나믹 프로그래밍이라는 알고리즘 기법입니다. 

 

일단 코드는 다음과 같습니다.

코드

#include <iostream>
using namespace std;
int main(void){
    int N = 6;
    int dp[255];
    dp[0] = 0; // fibo 1선언
    dp[1] = 1; // fibo 2선언
    for(int i = 2;i<=N;i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    cout << dp[N] <<"\n";
}

fibo(N) = fibo(N-1)+fibo(N-2)라는 점화식을 알아내서 fibo(2) ~ fibo(N)까지 순차적으로 구해나갔다.

이렇게 보면  fibo(2) ~ fibo(N)까지 순차적으로 구하는데 각각 한 번씩만 방문한다.

 

N이 작을 때는 시간이 별로 차이가 나지 않지만 N이 무수히 커지면 그 차이는 기하급수적으로 차이가 날 것이다.

왜냐하면 fibo 5를 구할 때와 fibo 6을 구할 때를 비교해봐도 호출하는 개수가 4개가 늘어나고 N이 커질수록 더 늘어나기 때문이다.

 

다이나믹 프로그래밍은 대회에서나 코딩 테스트에서 많이 물어보는 영역이므로 더욱더 열심히 해야 한다!!