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

 

동적 계획법 (Dynamic Programming)

  하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이기도 하다.

 

  상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법을 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없다.) 대표적인 예시로는 피보나치 수열이 있다.

 

  피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다. 만약 재귀함수만으로 프로그래밍을 한다면, 15번째 피보나치 수열의 값을 구하기 위해서는12번째 피보나치 수열값을 3번이나 계산하게 된다. 우리는 이런 불필요한 계산을 DP를 이용하여 없앨 수 있다.

 

DP는 다음의 가정 하에 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

Source Code 1 - 재귀만 이용

#include <stdio.h>

int d[100];

int dp(int x) {
    if(x == 1) return 1;
    if(x == 2) return 2;
    return dp(x - 1) + dp(x - 2);
}

Source Code 2 - DP까지 이용

#include <stdio.h>

int d[100]; //계산한 값을 저장할 배열

int dp(int x) {
    if(x == 1) return 1;
    if(x == 2) return 2;
    if(d[x] != 0) return d[x]; //이미 계산된 적이 있으면 저장 되어있는 값을 반환
    return d[x] = dp(x - 1) + dp(x - 2);
}