[알고리즘]동적계획법 (Dynamic Programming)

동적계획법 DP(Dynamic Programming) 이란 

어떤 문제를 풀기 위해 과거에 구한 해를 활용하는 방식의 알고리즘을 말한다.

말로 설명하면 이해하기 어려울 수 있기 때문에 가장 대표적인 예시 피보나치 수열을 살펴보겠다.

피보나치 수열은 첫항과 둘째항이 1, 1로 그다음 항부터는 앞의 두 항을 더하는 식이다.

f(n) = f(n-1) + f(n-2) 

수식으로 표현하면 위와 같다.

#include<iostream>
using namespace std;
int f[100]={0};
 
int fib(int n){
    if(n==0) return 0;
    else if(n==1) return 1;
    else if(f[n]) return f[n];
    else{
        f[n]=fib(n-1)+fib(n-2);
        return f[n];
    }
}
 
int main(){
    int N;
    cin>>N;
    cout<<fib(N);
    return 0;
}
 

위는 피보나치수열을 구현한 소스코드인데 동적계획법을 활용한 것이다. 

f라는 배열을 선언하여 계산의 반복을 줄이고자 f[n]에 값이 있으면 바로 반환하는 형식이다.

fib함수 내부를 살펴보면 쉽게 이해할 수 있다.

만약 배열을 사용하지 않고 재귀호출로만 구현한다면

연산량이 기하급수적으로 늘어난다.

아래 두 사진은 출력까지의 시간을 비교하기 위한 결과이다.

동적계획법을 사용하지 않았을 때와 사용했을 때 각각의 출력시간인데,

11.07초와 0.3626초로 그 차이가 매우 큼을 알 수 있다.

이와같이 수가 커질수록 동적계획법을 사용해야 훨씬 빠르게 해를 구할 수 있다.