DP - 다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍

동적 계획법이라고도 부르는 다이나믹 프로그램(DP)는 프로그래밍 대회에서 많이 나오는 문제이다. 다이나믹 프로그래밍이란 간단히 말해 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다.

 

일반적으로 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있는데, 그 예로 피보나치 수열을 들 수 있다.

피보나치 수열(D[i]=D[i-1]+D[i-2])은 특정한 순서의 숫자를 구하기 위해 한칸 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야하는 것인데 아래 그림으로 살펴보면 12와 13 등과 같이 동일한 것이 여러번 풀린다는 것을 쉽게 확인할 수 있다.

이 경우에는 이미 풀었던(해결한) 문제를 다시 반복적으로 풀기 때문에 비효율적이다. 그러므로 이를 해소하기 위해 다이나믹 프로그래밍을 사용하는데, 다이나믹 프로그래밍은 아래 두가지의 가정 하에 사용할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

즉, 크고 어려운 문제를 작고 쉬운 문제로 나누어 해결한 후 처리하여 전체의 답을 구하는 것이다. 이 과정에서 메모이에이션(Memoization)이 사용되는데, 이러한 점에서 다이나믹 프로그래밍이 분할 정복 기법과 다르다는 것을 알 수 있다.

 

그럼 간단한 피보나치 수열 문제를 예로 들어 살펴보자.

 

#include <stdio.h>
 
int d(int x) {
    if (x <= 2)
        return 1;
    return d(x - 1) + d(x - 2);
}
 
int main() {
    printf("%d", d(50));
}

 

위 코드는 분할 정복 기법을 사용한 경우로, d(n)에서 n의 크기가 클 경우 계산이 아주아주 오래 걸린다. 이 경우에는 피보나치 수열이 1개가 늘 때마다 계산량이 2배로 늘어나기 때문에, 계산해야할 수가 2의 n 제곱이라고 볼 수 있다.

그럼 메모이제이션을 사용한 다이나믹 프로그래밍 코드에 대해 살펴보자.

 

#include <stdio.h>
 
int d[100];
 
int fibo(int x) {
    if (x <= 2)
        return 1;
    if (d[x] != 0)
        return d[x];
    return d[x] = fibo(x - 1) + fibo(x - 2);
}
 
int main() {
    printf("%d", fibo(40));
}

 

위 코드와 같이 d라는 배열을 두어 배열에 계산한 값을 저장하고, 그 후에 해당 계산한 값이 다시 쓰일 경우 다시 계산하지 않고 계산한 값을 그대로 반환해주는 식으로 피보나치 수열을 구현하였다. 이 경우에는 각각의 계산이 1번만 수행되기 때문에 d(n)인 경우 n개의 계산만 수행하여 그 속도가 빠르다는 것을 알 수 있다.

 

이처럼 오늘은 다이나믹 프로그래밍에 대해서 알아보았다. 관련한 문제는 아래 링크를 참고하길 바란다.

[DP] 다이나믹 프로그래밍 타일링 문제 (11726, 11727, 2133) (tistory.com)

[DP] 다이나믹 프로그래밍 타일링 문제 (11726, 11727, 2133)