[Algorithm] 동적 계획법(DP, dynamic programming) 및 예시

---

동적 계획법 (DP)

 

최적화 이론 중 하나의 기술로 기존에 사용된, 즉 사전에 계산된(pre-computed) 값들을 재활용하는 방법이다. 즉 특정 알고리즘이라기 보다는 문제 해결 방식 중 하나이다. 다만 사전에 계산된 값들을 저장해두고 사용해야 하기 때문에 추가적인 메모리 사용이 필요하다.

구현 방식에서 분할 정복(divide and conquer)과 유사한 측면이 있다. 앞에서 설명한 것 처럼 주어진 문제를 나누어 보고, 이 중 기존 계산을 이용할 수 있는 것을 불러와 사용하기 때문이다.

그 방법에 따라 메모이제이션(memoization)과 타블레이션(tabulation)으로 나뉘는데 메모이제이션은 하향식(top-down)으로 보통 재귀 함수(recursion)와 함께 사용한다. 계산한 결과를 딕셔너리나 배열에 저장(caching)하여 다음에 같은 입력이 있을 때 저장한 값을 사용함으로써 효율을 높인다. 타블레이션은 상향식(bottom-up)으로 보통 반복문(iteration)과 함께 사용한다. 작은 문제부터 차례대로 해결해서 배열을 채워나가는 방식이다.

메모이제이션은 호출 스택을 사용하기 때문에 스택 오버플로우 위험이 있지만 간결하게 코드를 구성할 수 있고, 필요할 때만 저장하기 때문에 어떤 측면에서는 더 효율적일 수 있다. 반면 타블레이션은 모든 값을 미리 계산하여 저장한 후 사용하기 때문에 어떤 측면에서는 비효율적일 수 있지만, 스택을 사용하지 않기에 스택 오버플로우를 걱정할 필요가 없다는 장점이 있다.

가장 대표적으로 동적 계획법을 사용하는 것이 피보나치 계산이다. 알려진 바와 같이 피보나치 수열을 계산하려면 4번째 피보나치 수를 계산하기 위해 3번째 피보나치 수와 2번째 피보나치 수를 계산해야 하는데, 이때 3번째 피보나치 수 계산에는 다시 2번째 피보나치 수가 사용됨에도 따로 계산한다. 이를 미리 계산해놓는 방식으로 효율적으로 계산할 수 있다.

#define MAX 1000

int memo[MAX];

int fib(int n) {
    if (memo[n] != -1) {
        return memo[n];
    }
    if (n <= 2) {
        return 1;
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    printf("Fibonacci number F(%d) = %d\n", n, fib(n));
    return 0;
}

동적 계획법은 특정 방법론이기 때문에 어느 하나에 대한 답을 아는 것보다 다양한 문제를 풀이하면서 그 방법론을 익히는 것이 더 중요하다.

 

---

맨해튼 여행자 문제 (Manhattan Tourist Problem)

 

맨해튼 여행자 문제는 격자 모양의 도로에서 어떻게 이동해야 가장 최적으로 도달할 수 있는지를 다루는 문제이다. 맨해튼의 도로 구조가 격자 형태여서 이러한 이름이 붙었다.

예를 들어, 좌측 상단에서 출발하여 우측 하단으로 이동한다고 하자. 이때 여행자는 오른쪽 또는 아래쪽으로만 이동할 수 있으며, 각 간선에는 특정 가중치가 부여되어 있다. 이 가중치는 예를 들어 이동 거리, 비용, 혹은 방문 가능한 장소 수 등을 나타낼 수 있다. 여행자는 가능한 많은 보상을 얻기 위해 가중치의 합이 최대가 되도록 경로를 선택하고자 한다. 그렇다면 어떤 경로가 가장 최적일까.

가장 간단하게는 가능한 모든 경로를 탐색하고, 각 경로마다 가중치를 계산해볼 수 있겠다. 그런데 이 방법은 너무 많은 계산 비용이 든다. $ n \times m $ 의 맨해튼 거리가 있다고 하면, 이 거리를 이동하는 경우의 수는 $ \dfrac{(n+m)!}{n! \cdot m!} $ 이다. 간단하게 위와 같은 $ 4 \times 4 $ 거리에 대해서는 $ 70 $ 개의 경로가 존재하는 것이다.

또 다른 방법은 그리디 알고리즘(greedy algorithm)을 활용하는 것이다. 즉 각 단계에서 최선의 선택을 하는 방법으로 가중치를 최대로 한다고 할 때 아래와 같이 이동할 것이다.

같은 가중치인 경우 선택을 해야하는데, 여기서는 아래쪽으로 움직였다. 이렇게 가중치의 합을 계산해본다면 $ 15 $ 이다. 그런데 잘 보면 더 최적으로 움직이는 경로가 보인다. 즉 그리디 알고리즘으로는 적당히 괜찮은 경로는 찾을 수 있지만, 최적의 경로를 찾지는 못한다.

최적의 경로를 어떻게 구할지 생각해보면, 어느 위치에 도착하기 위해서는 그 전 위치가 고정된 것을 확인할 수 있다. 즉 $ (1, 1) $ 에 도달하기 위해서는 $ (1, 0) $ 혹은 $ (0, 1) $ 에서 출발해야 한다. 어차피 각 간선의 가중치는 고정되어 있으니 $ (1, 1) $ 에서 생각해보면 $ (1, 0) $ 과 $ (0, 1) $ 중 해당 지점까지의 가중치의 합과 그 지점에서 $ (1, 1) $ 에 도착하는 간선을 거치며 얻어지는 가중치를 더해 더 큰 가중치를 가지는 경로를 선택하면 된다. 그렇다면 다시 $ (1, 0) $ 과 $ (0, 1) $ 을 비교해야 한다. $ (0, 1) $ 의 입장에서 생각해본다면 $ (0, 0) $ 에서 올 수 밖에 없다. 따라서 $ (0, 0)$ 에 도착했을 때의 가중치의 합은 고정되어 있다. $ (1, 0) $ 역시 마찬가지이다. 그렇다면 각 지점마다 최대 가중치 합을 직전 지점에서의 최대 가중치 합과 간선의 가중치를 이용하여 구할 수 있고, 이렇게 되면 분할 정복과 유사하게 문제를 나눠서 볼 수 있게 된다.

즉 차례대로 각 지점에서의 최대 가중치 합을 써주면 된다. 물론 이렇게 되면 메모리는 더 이용될 것이다.

이를 활용하여 최적의 경로를 표현하면 위와 같다. 물론 그리디 알고리즘보다 계산도 더 많이 하고, 추가적인 메모리도 필요하지만, 최적의 경로를 구할 수 있는 것이다.

그래프를 어떻게 구현하느냐에 따라 코드가 달라지므로 코드는 따로 첨부하지 않았다.

 

---

동전 교환 문제 (Coin Change Problem)

 

주어진 동전 종류들로 특정 금액을 만들 때, 필요한 최소 동전 개수를 구하는 문제이다. 일상생활에서 동전은 $ 10 $원, $ 50 $원, $ 100$원과 같이 상위 동전이 하위 동전의 배수로 되어 있어 값이 큰 동전부터 차례대로 계산하면 최소 동전 개수를 구할 수 있다. 즉 그리디 알고리즘을 이용할 수 있다.

그러나 주어진 동전이 배수 관계가 아니라 $ \{ 1, 3, 4 \} $ 이고 특정 금액이 $ 6 $ 원이라 생각해보자. 그리디 알고리즘을 사용하면 먼저 $ 4 $ 원 동전으로 계산하여 동전 $ 1 $ 개를 사용하고, $ 1 $ 원 동전을 $ 2 $ 개 사용하여 총 $ 3 $ 개의 동전이 필요하다. 그런데 $ 3 $ 원 $ 2 $ 개를 통해 $ 6$ 원을 만들 수 있으므로 이는 최적의 값을 구하는 방법이 아니다.

그렇다고 각 특정 금액마다 경우의 수를 모두 구해 그 중 최소값을 찾아내는 것 역시 굉장히 많은 계산 비용이 들어간다. 금액이 $ M $ 이고 동전 단위가 $ d $ 개 일 때 모든 경우의 수를 구하는 완전 탐색(exhaustive search)의 최악의 경우 시간복잡도는 $ O(M^d) $ 이다. 그리디 알고리즘의 시간복잡도를 $ O(d) $ 정도로 만들 수 있다는 것을 생각하면 완전 탐색은 실제로 사용하는 어려워보인다.

이 경우 분할 정복을 고려해보자. 간단하게 예시로 특정 금액이 $ M = 11 $ 이라 하고, 동전이 $ c = \{ 1, 3, 5 \} $ 라 해보자. 그렇다면 $ 11 $ 을 만들기 위해서는 어떻게 해야할까. 특정 동전 하나를 더해서 $ 11 $ 을 만든다고 생각해보면 $ 11 $ 을 만들 수 있는 경우의 수는 $ c $ 의 개수인 $ d = 3 $ 만큼 있다. 즉 $ 11 - 1 = 10 $ 에 $ 1 $ 을 더해 $ 11 $ 을 만드는 방법, $ 11 - 3 = 8 $ 에 $ 3 $ 을 더해 $ 11 $ 을 만드는 방법, $ 11 - 5 = 6 $ 에 $ 5 $ 를 더해 $ 11 $ 을 만드는 방법이 있다.

그렇다면 다시 각각 $ 10 $, $ 8 $, $ 5 $ 를 만드는 방법은 무엇이 있을까. 가장 쉬운 $ 5 $ 를 생각해본다면 $ 5 - 5 = 0 $ 에 $ 5  $를 더하는 방법, $ 5 - 3 = 2 $ 에 $  3 $ 을 더하는 방법, $ 5 - 1 = 4 $ 에 $ 1 $ 를 더하는 방법이 있다. 이 경우 다른 것보다 $ 5 $ 원 하나만 가지고 있는 경우가 동전 개수를 최소로 만든다는 것을 알 수 있다. 같은 방법으로 $ 8, 10 $ 역시 최소 동전 개수를 구해준다면 $ 11 $ 을 구성하기 위해 필요한 최소 동전 개수 역시 구할 수 있다.

이를 특별히 생각하지 않고, 재귀로 구현해보자. 그렇다면 다음과 같다.

int get_min_coins(int M, const vector<int>& coins) {
    if (M == 0) {
        return 0;
    }
    int min_coins = INT_MAX;
    for (int coin : coins) {
        if (M - coin >= 0) {
            int res = get_min_coins(M - coin, coins);
            if (res != INT_MAX) {
                min_coins = min(min_coins, 1 + res);
            }
        }
    }
    return min_coins;
}

그런데 재귀로 구현하면 처음 예시로 설명한 피보나치 계산과 마찬가지로 중복된 계산이 많아진다. 따라서 메모리를 더 사용하더라도 이미 계산된 상황, 앞선 예시에서는 $ 5 $, $ 8 $ 등을 구할 때 이미 최소 동전 개수를 구해놓았으므로 이를 저장해두고 사용하면 계산 비용을 줄일 수 있다.

int get_min_coins(int M, const vector<int>& coins, vector<int>& dp) {
    if (M == 0) {
        return 0;
    }
    if (dp[M] != -1) {
        return dp[M];
    }
    int min_coins = INT_MAX;
    for (int coin : coins) {
        if (M - coin >= 0) {
            int res = get_min_coins(M - coin, coins, dp);
            if (res != INT_MAX) {
                min_coins = min(min_coins, 1 + res);
            }
        }
    }
    dp[M] = min_coins;
    return dp[M];
}

이렇게 하면 시간복잡도가 $ O(M \times d) $ 로 완전 탐색보다 효율적이면서 그리디 알고리즘과 달리 최적의 값을 도출할 수 있다.

 

---

돌 게임 문제 (Move Rocks Problem)

 

두 사람이 돌을 가지고 게임을 하는데, 두 개의 돌 더미가 있으며 각각 $ m $ 개와 $ n $ 개의 돌이 있다. 한 번의 턴에서 다음 중 하나의 동작만 할 수 있다.

1. 한 더미에서 돌 1개 제거
2. 각각의 더미에서 돌 1개씩 제거, 즉 돌 2개 제거

제거된 돌은 다시 돌려놓을 수 없고, 마지막 돌을 제거한 사람이 승리한다. 그렇다면 $ n $ 과 $ m $ 이 주어질 때 처음 시작하는 사람이 이기는지 지는지 어떻게 확인할 수 있을까. 물론 여기서는 두 사람이 최선의 선택을 한다고 가정한다.

이는 2차원 테이블을 그려 확인할 수 있다. 테이블에 행은 $ m $, 열은 $ n $ 으로 놓고 각 경우에 누가 이기는지 확인하는 것이다. 간단하게 아래와 같이 그릴 수 있다. 시작하는 사람이 이기면 W라 표기한다.

	0	1	2	3	4	5	6	7	8
0		W	L
1	W	W
2	L
3
4
5
6
7
8

두 개의 돌더미에 $ 1 $ 개씩 있던, 둘 중 하나의 돌더미에 $ 1 $ 개만 있던 시작하는 사람이 이긴다. 혹은 하나의 돌 무더기에 $ 2 $ 개 돌이 있는 경우 처음 시작하지 않은 사람이 이긴다. 다음은 어떻게 될까.

	0	1	2	3	4	5	6	7	8
0		W	L	W
1	W	W	W
2	L	W
3	W
4
5
6
7
8

돌이 늘어난 경우를 생각해보면 위와 같을 것이다. 각 경우를 하나하나 확인하면서 따져보자. 먼저 $ n $ 에는 돌이 $ 2 $ 개 있고, 다른 무더기 $ m $ 에 돌이 $ 1 $ 개 있는 경우 처음 사람의 선택은 $ 3 $ 개로 나뉜다. 돌무더니 $ n $ 에서 가져가는 것, $ m $ 에서 가져가는 것, $ n $ 과 $ m $ 에서 가져가는 것. 그런데 $ n $ 에서 가져가면 그 후에는 각각의 돌무더기에 $ 1 $ 개씩 돌이 남게된다. 이는 다음 사람 입장에서는 각각의 돌무더기에 $ 1 $ 개씩 돌이있는 상황에서 게임을 시작하는 것과 마찬가지이다. 즉 시작하지 않는 사람이 이긴다. $ m $ 에서 가져가면 그 다음에는 $ n $ 에 돌이 $ 2 $ 개 남으므로 처음 시작하는 사람이 이긴다. 두 돌무더기에서 $ 1 $ 개씩 가져가면 처음시작하지 않는 사람이 이긴다.

이를 위 테이블로 표현해보면 좌측, 좌상단, 상단으로 움직이는 선택지가 주어진다고 생각할 수 있다. 그런데 해당 선택지 중에 자신이 이기는 선택지를 선택할 것이다. 그렇다면 이는 위 테이블을 이용하는 문제로 생각할 수 있다. 즉 선택지 모두가 자신이 지는 선택지라면 지는 것이고, 하나라도 이기는 선택지가 있다면 이기는 것이다.

단 한 번 움직일 때 시작하는 사람 입장이 바뀐다는 것을 생각해야 한다. 예를 들어서 $ m = 2 $, $ n = 1 $ 이라 해보자. 그렇다면 해당 사람은 좌측, 좌상단, 상단에 L이 있나 확인해야 한다. 만약 L이 있으면 W인 것이고, 모두 W라면 L인 것이다. 즉 다음 턴에 상대가 지는 경우의 수가 있다면 내가 이기는 것이고, 상대가 모두 이기는 경우의 수 밖에 없다는 내가 지는 것이다.

이를 이용하여 다시 테이블을 채우면 아래와 같다.

	0	1	2	3	4	5	6	7	8
0		W	L	W	L	W	L	W	L
1	W	W	W	W	W	W	W	W	W
2	L	W	L	W	L	W	L	W	L
3	W	W	W	W	W	W	W	W	W
4	L	W	L	W	L	W	L	W	L
5	W	W	W	W	W	W	W	W	W
6	L	W	L	W	L	W	L	W	L
7	W	W	W	W	W	W	W	W	W
8	L	W	L	W	L	W	L	W	L

이러한 테이블을 구하는 코드는 아래와 같이 구성할 수 있을 것이다.

vector<vector<char>> get_winner(int n, int m) {
    vector<vector<char>> R(n + 1, vector<char>(m + 1));
    R[0][0] = 'L';
    for (int i = 1; i <= n; ++i) {
        R[i][0] = (R[i - 1][0] == 'W') ? 'L' : 'W';
    }
    for (int j = 1; j <= m; ++j) {
        R[0][j] = (R[0][j - 1] == 'W') ? 'L' : 'W';
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (R[i - 1][j - 1] == 'W' &&
                R[i][j - 1] == 'W' &&
                R[i - 1][j] == 'W') {
                R[i][j] = 'L';
            } else {
                R[i][j] = 'W';
            }
        }
    }
    return R;
}