동적 계획법(Dynamic Programming)
개발/알고리즘

동적 계획법(Dynamic Programming)

피보나치 수열은 다음 점화식을 통해 나타낼 수 있다.

 

$$F_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if }n = 1 \\ F_{n-1} + F_{n-2} & \text{if }n > 1 \end{cases}$$

 

그대로 재귀함수로 구현하면 다음과 같다.

int fibo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibo(n-1) + fibo(n-2);
}

 

이 함수는 작은 $n$에 대해서는 빠르게 계산된다. 하지만 $50$을 넣으면 1초 안에 답이 나올까? 아마 나오지 않을 것이다. 그러면 입력값에 따른 총 함수 호출 횟수를 계산해보자.

int cnt;

int fibo(int n) {
    cnt++;
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibo(n-1) + fibo(n-2);
}

 

$40$을 넣으면 cnt의 값은 $331\,160\,281$이 된다. 이 값은 $(\sum_{n=0}^{40}{F_n}) + F_{39}$이다. 즉 fibo(n)을 계산하는 데 드는 연산 횟수는 피보나치 수에 비례하고, 피보나치 수는 지수 식을 띄는 일반항을 가지므로 결국 지수 시간 복잡도를 가진다.

 

이렇게 많은 연산량을 필요로 하는 이유가 무엇일까? 바로 중복된 함수 호출이다. fibo(5)를 실행했을 때 호출되는 함수들은 아래 그림과 같다.

 

중복되는 부분 문제

 

서로 중복되는 부분 문제가 너무 많다. 사실 $F_2$의 값은 몇 번을 계산해도 항상 $1$일 것이기 때문에 굳이 여러 번 반복해서 계산할 필요가 없다. 그래서 이미 계산된 부분 문제의 답들을 저장해 놓고 다시 사용하면 시간 복잡도를 획기적으로 단축할 수 있게 된다.

int cnt;
int dp[45];

int fibo(int n) {
    cnt++;

    int &ret = dp[n];
    if (ret != -1) return ret;

    if (n == 0) return ret = 0;
    if (n == 1) return ret = 1;
    return ret = fibo(n-1) + fibo(n-2);
}

int main() {
    memset(dp, -1, sizeof(dp)); // 피보나치에서 절대 나올 수 없는 값인 -1로 초기화

    int n; cin >> n;
    cout << fibo(n) << ' ' << cnt;
}

 

$40$을 입력하면 cnt 값은 $79$다. 어떠한 값을 입력하더라도 함수 호출의 횟수는 $2n-1$번이 되고, 시간 복잡도는 $O(n)$이 된다. 지수 시간에서 선형 시간으로 줄어든 것을 확인할 수 있다.

 

동적 계획법(Dynamic Programming, DP)은 이처럼 주어진 문제를 여러 개의 문제로 나누어 푼 다음 그 결과로 주어진 문제의 답을 얻는 문제 해결 기법이다. 분할 정복과 비슷하지만 결정적인 차이점이 한 가지 있다.

 

분할 정복은 겹치는 부분 문제가 없기 때문에 부분 문제의 답을 저장할 필요가 없지만, 동적 계획법에서는 겹치는 부분 문제가 존재하기 때문에 한 번만 부분 문제를 풀고 이를 저장하는 메모이제이션(Memoization) 과정이 필요하다.

탑다운과 바텀업

동적 계획법을 이용해 문제를 풀 때는 주로 두 가지 방식을 이용한다. 첫 번째는 위의 fibo 함수처럼 재귀 호출을 이용해서 큰 문제부터 방문하는 탑다운(Top-down) 방식이고, 두 번째는 반복문을 이용하여 작은 문제부터 답을 쌓아 올려 나가는 바텀업(Bottom-up) 방식이다.

 

fibo 함수를 바텀업 방식으로 다음과 같이 구현할 수 있다.

int dp[45];

int main() {
    memset(dp, -1, sizeof(dp));

    int n; cin >> n;

    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
}

 

탑다운 방식의 장점은 점화식을 이해하기 조금 더 쉽고 가독성 측면에서 바텀업 방식에 비해 약간 낫다는 것이다. 반면 바텀업 방식은 함수 호출 비용이 없기 때문에 시간과 메모리를 조금 더 적게 사용한다.

    티스토리툴바