[DP] 동적 프로그래밍 | 동적 계획법 Dynamic Programming

동적 프로그래밍(동적 계획법, Dynamic Programming)은 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이고, Subproblem은 반복되며 답은 항상 같은 특성을 이용하여 Memoization을 통해 최종적으로 문제를 해결하는 것을 말한다.

---

설명

간략하게 정리된 위의 문장을 쪼개서 설명하면 다음과 같다.

1. 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이다.

 하나의 문제를 풀기 위해서는 그보다 더 작은 Subproblem으로, 그리고 해당 subproblem에서 그보다 더 작은 Subproblem을 더이상 나눌 수 없을 때까지 나누어 작은 Subproblem의 결과 값으로 부터 최종 답을 구할 수 있는 경우에 사용하면 좋다.

 예를 들면, F(3)의 답을 구하기 위해서는 F(2)과 F(1)의 답을 먼저 알아야 하는 경우이다. 즉, 이 경우 F(3)의 Subproblem은 F(2), F(1)이다.

 

2.  Subproblem은 반복되며 답은 항상 같다.

 위의 예시에 이어 설명하자면, 만약 F(4)의 답을 구하기 위해서는 F(3)과 F(2)의 답을 알아야하며, 이때 F(4)의 Subproblem은 F(3), F(2)이다. 그리고 F(3)의 Subproblem은 F(2), F(1)이었으니 결국, F(2)를 구하는 과정이 2번 반복된다. 그리고 반복되더라도 F(2)의 결과 값은 항상 같다는 것을 의미한다.

 

3. Memoization

Subproblem의 결과 값을 저장해서 사용한다. 즉, 한 번 계산이 이뤄지면 같은 값을 반복적으로 계산하지 않는다.

이는 1.과 2.에서 설명한 특성 덕분에 적용 가능하다. 위의 예시처럼 F(2) 값을 2번 구하는 과정이 필요하나 그 값은 항상 같기 때문에 한 번 F(2)의 결과 값을 구하면 따로 저장해두었다가 그 값을 활용해 계산 과정을 다시 밟을 필요가 없어지는 것이다.

 

따라서, 동적 프로그래밍의 장점이 Memoization 특성에서 나온다.

 

---

사용 예제

DP 알고리즘의 대표적인 사용 예제는 피보나치 수(Fibonacci numbers)로 들 수 있다.

 

피보나치 수는 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ∙∙∙

0번째 항은 0, 1번째 항은 1이고, 그 이후의 항은 바로 앞 두 항의 합인 수열이다.

따라서, 이를 두개의 항 사이에 성립하는 관계를 나타낸 점화식으로 다음과 같이 표현한다.

자, 그럼 피보나치 수를 DP 알고리즘에 적용할 수 있는지를 살펴보자.

1. 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이다.

F(5) = F(4) + F(3)이다. 즉, F(5)의 Subproblem은 F(4), F(3)이다.

 

2.  Subproblem은 반복되며 답은 항상 같다.

F(4) = F(3) + F(2)의 경우에도 F(3)이 F(4)의 Subproblem이며, F(3)의 값은 항상 F(2)+F(1) = 2로 같다.(F(1) = 1, F(2) = F(1) + F(0) = 1 + 0 = 1)

 

3. Memoization

따라서, 반복적으로 발생하는 Subproblem을 매번 구하지 않고, 이전에 한 번 구한 값을 어딘가에 저장을 해서 반복적으로 사용하면 좋다.

 

---

구현 방법

그렇다면, DP 알고리즘을 어떻게 구현하는 지를 공부해보자.

DP 알고리즘의 구현 방법은 크게 Bottom-up과 Top-down로 나뉜다.

이는 Subproblem을 어떻게 나눠 가느냐에 따라 다르다.

그리고 문제에 따라 Bottom-up 방법을 써야하는 경우, Top-down 방법을 써야하는 경우, 둘 중 어느 것을 사용해도 상관 없는 경우로 나뉠 수 있다.

 

• Bottom-up의 경우, 가장 작은 Subproblem부터 차례로 구해나가 최종 문제의 답을 구하는 방법이다. 반복문을 사용한다.
• Top-down의 경우 반대로, 최종 문제을 Subproblem으로 나눈 후, 또 해당 Subproblem의 Subproblem으로 나눠가면서 답을 구해나가 모든 Subproblem의 답을 구해 최종 답을 구하는 방법이다. 재귀를 사용한다.

 

이 역시 피보나치의 수 F(5)를 구하는 예로 쉽게 설명하자면,

 

• Bottom-up

F(0)부터 F(4)까지 차례로 값을 구하고 저장한 후, 저장된 F(4), F(3) 값을 더해 최종적으로 F(5)를 구하는 것이다.

이를 코드로 나타내면 다음과 같다.

 

//
//  main.cpp
//  bottomup
//
//  Created by Hwayeon on 2021/03/19.
//

#include <iostream>
using namespace std;

int dp[100] = {0, 1, };

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

int main(int argc, const char * argv[]) {
    int n, answer;
    cin >> n;
    for(int i=0; i<=n; i++){
        answer = fibo_dp(i);
        cout << "f(" << i << ") = " << answer << endl;
    }

    return 0;
}

 

 

• Top-down

F(5)의 값을 구하기 위해 Subproblem인 F(4), F(3)으로 쪼개고, F(4)를 F(3), F(2)로, F(3)을 F(2), F(1)로 쪼개나가면서 해당 Subproblem의 값이 저장된 경우(이전에 이미 계산된 경우), 값을 불러오면서 최종적으로 F(5)를 구하는 것이다.

이를 코드로 나타내면 다음과 같다.

//
//  main.cpp
//  topdown
//
//  Created by Hwayeon on 2021/03/19.
//

#include <iostream>
using namespace std;
int dp[100] = {0, 1, };

int fibo_dp(int n){
    if(n <= 1) return n;
    if(dp[n] != 0) return dp[n];

    dp[n] = fibo_dp(n-1) + fibo_dp(n-2);
    
    return dp[n];
}

int main(int argc, const char * argv[]) {
    int n, answer;
    cin >> n;
    for(int i=0; i<=n; i++){
        answer = fibo_dp(i);
        cout << "f(" << i << ") = " << answer << endl;
    }
    return 0;
}

 

---

참고

• ko.wikipedia.org/wiki/피보나치_수

피보나치 수