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

반응형

 

동적 계획법(Dynamic Programming)

큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure)라고 한다. 이 최적 부분 구조가 지켜진 상태에서 문제에 대한 해답을 찾는 과정이 바로 동적 계획법이다.

 

동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 예시로 피보나치 수를 보자. 피보나치 수는 다음과 같다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

이를 점화식으로 나타내면 다음과 같다.

$$\begin{align} f(1) & = f(2) = 1 \\ f(n) & = f(n-1) + f(n-2) \end{align}$$

\(n\)의 피보나치 수는 더 작은 크기인 \(n-1\)의 피보나치 수와 \(n-2\)의 피보나치 수를 포함하고 있다. 즉, 최적 부분 구조를 가졌다. 이런 경우에는 재귀함수를 사용해 간단하게 표현할 수 있다.

int fibonacci(int n) {
    if (n = 1 || n = 2) {
        return 1;
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

그런데 피보나치 수를 재귀함수를 이용해 구하는 방법은 매우 비효율적이다. 아래의 그림은 피보나치 수 6을 구하는 과정에서 호출된 함수들을 나타낸 것이다.

 

fibonacci(6)을 구하는 과정

수가 커짐에 따른 fibonacci(2)의 호출 수의 증가

같은 함수가 중복해서 호출되는 것이 보인다. fibonacci(2)의 경우를 보자면(아래의 표) 크기가 점점 커질수록 중복 호출이 약 \(2^{n \over 2}\)만큼증가한다. 

 

동적 계획법은 이런 중복 호출로 인한 효율이 떨어지는 경우에서 사용할 수 있는 방법이다. 즉, 최적 부분 구조를 이루면서 재귀적으로 구현했을 때 효율성이 떨어지는 문제를 해결하는 것이 동적 계획법이라고 할 수 있겠다.

 

피보나치 수를 계속해서 예로 들자면, 중복 호출을 예방해주기 위해 이미 호출된 값을 저장해주는 방법을 생각해보자. 이미 호출된 값을 기록해놓으면 반복 호출을 막을 수 있다. 이처럼, 이전에 호출된 적이 있는 것을 저장하는 방법으로 중복 호출을 피하는 것을 메모이제이션(Memoization)이라고 한다. 메모이제이션은 동적 계획법의 핵심이 된다. 피보나치 수에 이 방법을 적용해보자.

 

1) 재귀함수

int f[10000];

int fibonacci(int n) {
    if (f[n] != 0) {
        return f[n];
    }
    else {
        if (n == 1 || n == 2) {
            f[n] = 1;
        }
        else {
            f[n] = fibonacci(n - 1) + fibonacci(n - 2);
        }
        return f[n];
    }
}

2) for문 사용

int fibonacci(int n){
    for (int i = 1; i <= n; i++) {
        if (i <= 2) {
            f[i] = 1;
        }
        else {
            f[i] = f[i - 1] + f[i - 2];
        }
    }
    return f[n];
}

f배열을 10000으로 선언은 했지만, 실제로는 n이 36을 넘어가는 순간 오버플로우가 발생한다. unsigned long long으로 해도 500보다도 더 낮은 수에서 오버플로우가 발생한다.

 

이렇게 된다면 두 함수 모두 선형 시간을 보장한다. 메모이제이션도 1)의 경우처럼 위에서 아래로 저장해나가는 방식을 탑다운(Top-down) 방식이라고 하고, 2)의 경우처럼 아래에서 위로 저장해나가는 방식을 바텀업(Bottom-up) 방식이라고 한다. 풀이에 큰 수가 먼저 시작되냐(Top-down), 작은 수가 먼저 시작되냐(Bottom-up)인 것이다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90