DP 상태·점화식·계산 순서

불변조건·종료와 반례 찾기에서 동전 [4, 3, 1]로 6을 만들 때, 큰 동전부터 고르는 탐욕법은 4 + 1 + 1의 세 개를 내놓았지만 3 + 3의 두 개가 더 적었습니다. 탐욕법은 지금 가장 좋아 보이는 선택을 하고 되돌아보지 않으므로, 처음 고른 4가 나중의 더 좋은 조합을 막아 버린 것입니다. 정확한 답을 얻으려면 가능한 선택을 모두 비교해야 하는데, 그대로 하면 경우의 수가 금액에 따라 폭발적으로 늘어납니다. 이 글에서는 같은 계산을 되풀이하지 않도록 작은 문제의 답을 표에 저장해 두고 쓰는 동적 계획법(dynamic programming, DP)으로 이 문제를 풉니다. 동적 계획법은 그 자체가 하나의 알고리즘이라기보다 문제를 나누고 답을 저장하는 설계 방법이라서, 상태와 점화식을 정하는 과정을 차근차근 익히는 것이 중요합니다.

모든 경우를 따지면 같은 계산을 되풀이한다

금액 x를 만드는 최소 동전 개수를 구하는 가장 직접적인 방법은 마지막에 낼 동전을 하나씩 정해 보는 것입니다. 마지막 동전이 c라면 나머지 금액 x - c를 가장 적은 개수로 만들고 c 하나를 더하면 됩니다. 마지막 동전으로 가능한 모든 c에 대해 이 값을 구해 가장 작은 것을 고르면 답입니다. 이 생각을 재귀로 그대로 옮기면 다음과 같습니다.

import math

calls = 0


def min_coins_naive(amount, coins):
    global calls
    calls += 1
    if amount == 0:
        return 0
    best = math.inf
    for coin in coins:
        if coin <= amount:
            best = min(best, min_coins_naive(amount - coin, coins) + 1)
    return best


for amount in [6, 10, 15, 20]:
    calls = 0
    result = min_coins_naive(amount, [4, 3, 1])
    print(amount, result, calls)

6 2 24
10 3 168
15 4 1869
20 5 20736

global calls는 함수 안에서 바깥의 변수 calls를 고치겠다는 선언으로, 호출 횟수를 세는 데 썼습니다. 답은 맞지만 금액이 20만 되어도 함수를 2만 번 넘게 부릅니다. 금액이 5 늘 때마다 호출이 열 배 넘게 늘어나므로, 금액이 100이면 현실적인 시간 안에 끝나지 않습니다.

호출이 이렇게 많은 이유는 같은 금액을 여러 번 다시 풀기 때문입니다. 20에서 4를 빼고 3을 빼도 13이고, 3을 빼고 4를 빼도 13이며, 1을 일곱 번 빼도 13입니다. 이 함수는 13을 만드는 최소 개수를 만날 때마다 처음부터 다시 계산합니다. 하지만 13을 만드는 최소 개수는 어떤 길로 13에 도착했든 늘 같습니다. 그렇다면 한 번 구한 답을 어딘가에 적어 두고, 다음부터는 계산하지 않고 꺼내 쓰면 됩니다. 이렇게 작은 문제들이 서로 겹치는 성질을 중복 부분 문제(overlapping subproblems)라고 합니다.

상태와 점화식

답을 적어 둘 표를 만들려면 표의 한 칸이 무엇을 뜻하는지부터 정해야 합니다. 이것을 상태(state)라고 합니다. 여기서는 best[x]를 "금액 x를 만드는 데 필요한 최소 동전 개수"로 정합니다. 금액 0은 동전 없이 만들 수 있으므로 best[0] = 0이고, 어떤 동전으로도 만들 수 없는 금액은 무한대로 둡니다.

다음으로 한 상태의 답을 더 작은 상태들의 답으로 나타내는 식을 세웁니다. 이것을 점화식(recurrence)이라고 합니다. 앞의 재귀가 한 일 그대로, 마지막 동전 c를 정하면 남은 금액 x - c는 x보다 작은 상태이므로 다음 식이 나옵니다.

best[x] = min(best[x - c] + 1)   (c는 x 이하인 모든 동전)

동전 [4, 3, 1]로 6을 만드는 경우, 마지막 동전이 4이면 best[2] + 1, 3이면 best[3] + 1, 1이면 best[5] + 1이 후보이고 그중 가장 작은 값이 best[6]입니다. 아래 그림은 6의 답이 이미 계산된 2, 3, 5의 답에 기대는 모습입니다.

계산 순서와 선택 복원

점화식이 정해지면 표를 채우는 순서를 정합니다. best[x]는 x보다 작은 금액의 칸만 읽으므로, 금액 0부터 차례로 올라가며 채우면 필요한 칸이 늘 먼저 채워져 있습니다. 동전이 모두 양수라는 조건이 이 순서를 가능하게 합니다.

표에는 개수만 적혀 있지만, 어떤 동전들을 내야 하는지도 알고 싶습니다. 그러려면 칸을 채울 때 가장 좋았던 마지막 동전을 previous[x]에 함께 기록해 둡니다. 다 채운 뒤에는 목표 금액에서 시작해 previous가 가리키는 동전을 하나씩 빼 가면, 최적 구성을 마지막 동전부터 거꾸로 얻을 수 있습니다. 6은 previous[6] = 3이므로 3을 빼서 3이 되고, previous[3] = 3이므로 다시 3을 빼서 0이 됩니다.

import math


def minimum_coins(amount, coins):
    if amount < 0 or any(coin <= 0 for coin in coins):
        raise ValueError("금액은 0 이상, 동전은 양수여야 합니다")
    best = [0] + [math.inf] * amount
    previous = [None] * (amount + 1)
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1
                previous[value] = coin
    if best[amount] == math.inf:
        return None
    result = []
    while amount > 0:
        coin = previous[amount]
        result.append(coin)
        amount -= coin
    return result


print(minimum_coins(6, [4, 3, 1]))
print(minimum_coins(20, [4, 3, 1]))
print(minimum_coins(7, [4, 6]))
print(minimum_coins(0, [4, 3, 1]))

[3, 3]
[4, 4, 4, 4, 4]
None
[]

재귀가 2만 번 넘게 호출한 금액 20을, 표는 금액 20개와 동전 3개의 조합인 60번의 확인으로 끝냅니다. [4, 6]으로는 7을 만들 수 없어서 best[7]이 무한대로 남고, 함수는 None을 돌려줍니다. 금액 0은 동전을 하나도 내지 않으면 되므로 빈 리스트입니다. 같은 개수의 구성이 여러 개라면 < 비교 때문에 동전 목록에서 먼저 나온 동전으로 만든 구성이 남습니다.

왜 맞는가

이 방법이 맞는 이유는 최적의 답이 반드시 점화식의 후보 가운데 하나라는 데 있습니다. 금액 x를 가장 적은 동전으로 만든 구성에서 마지막 동전 c를 하나 빼면, 남은 동전들은 금액 x - c를 만듭니다. 이 남은 부분은 x - c를 만드는 최적 구성이어야 합니다. 만약 x - c를 더 적은 동전으로 만드는 방법이 있다면, 그것에 c를 더해 x를 원래보다 적은 동전으로 만들 수 있어서 처음 구성이 최적이라는 가정과 맞지 않기 때문입니다. 이처럼 최적의 답 안에 들어 있는 작은 문제의 답도 최적이라는 성질을 최적 부분 구조(optimal substructure)라고 합니다.

따라서 최적 구성의 개수는 어떤 c에 대한 best[x - c] + 1과 같고, 점화식은 모든 c를 비교하므로 그 값을 놓치지 않습니다. 작은 금액부터 채우므로 best[x - c]는 x를 계산할 때 이미 맞는 값이고, 귀납법으로 모든 칸이 맞습니다. 복원할 때는 금액이 양수인 동전만큼 줄어들므로 반드시 0에 도착해 끝납니다. 동전 0을 허용하면 x - 0 = x가 자기 자신을 가리켜 이 순서가 무너지므로, 함수는 처음에 양수가 아닌 동전을 거절합니다.

동적 계획법을 설계하는 순서

이 글에서 한 일을 일반적인 순서로 정리하면 다음과 같습니다. 이 순서는 뒤의 피보나치 수와 LCS, 그리고 앞 장의 Floyd–Warshall 알고리즘에도 똑같이 적용됩니다.

1. 표의 한 칸, 곧 상태가 무엇을 뜻하는지 한 문장으로 정한다.
2. 마지막에 하는 선택을 기준으로 경우를 나누어, 한 상태를 더 작은 상태들로 나타내는 점화식을 세운다.
3. 더 나눌 수 없는 기저 사례의 값을 정한다.
4. 각 상태가 기대는 상태가 먼저 계산되도록 계산 순서를 정한다.
5. 값뿐 아니라 실제 선택이 필요하면, 칸마다 고른 선택을 기록해 거꾸로 따라가며 복원한다.

동적 계획법이 통하려면 두 성질이 필요합니다. 같은 작은 문제가 여러 번 나오는 중복 부분 문제가 있어야 저장해 두는 보람이 있고, 최적의 답이 작은 문제의 최적 답으로 이루어지는 최적 부분 구조가 있어야 점화식이 맞습니다.

비용과 적용 범위

금액이 A이고 동전이 C종류이면, 칸 A개마다 동전 C개를 확인하므로 시간은 O(AC)입니다. 공간은 best와 previous의 O(A)이고, 복원은 답의 동전 개수만큼 걸립니다. 이 비용은 금액 A의 크기에 비례한다는 점에 주의해야 합니다. 금액이 1조라면 표에 칸이 1조 개 필요해서 현실적으로 계산할 수 없습니다. 입력의 길이는 금액의 자릿수 정도인데 비용은 금액 자체에 비례하므로, 이런 비용을 의사 다항 시간(pseudo-polynomial time)이라고 부릅니다.

더 깊이: 개수 대신 방법의 수를 세면

같은 동전 문제라도 묻는 것이 바뀌면 상태와 계산 순서도 바뀝니다. 동전 [1, 2, 5]로 금액 5를 만드는 방법이 몇 가지인지 세어 봅시다. 동전의 순서를 따지지 않는다면 5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1의 네 가지입니다. 그런데 2 + 1 + 1 + 1과 1 + 2 + 1 + 1처럼 내는 순서가 다른 것을 다른 방법으로 센다면 아홉 가지가 됩니다.

def count_combinations(amount, coins):
    ways = [1] + [0] * amount
    for coin in coins:
        for value in range(coin, amount + 1):
            ways[value] += ways[value - coin]
    return ways[amount]


def count_sequences(amount, coins):
    ways = [1] + [0] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value:
                ways[value] += ways[value - coin]
    return ways[amount]


print(count_combinations(5, [1, 2, 5]), count_sequences(5, [1, 2, 5]))

4 9

두 함수의 차이는 반복의 순서뿐입니다. count_combinations는 동전을 바깥 반복에 두어, 동전 1만 쓰는 방법을 모두 센 뒤 동전 2를 더 쓰는 방법을, 그다음 동전 5를 더 쓰는 방법을 셉니다. 그래서 같은 동전 묶음은 동전 목록의 순서대로 한 번만 세어집니다. count_sequences는 금액을 바깥 반복에 두어, 금액마다 마지막에 낸 동전이 무엇인지로 경우를 나누므로 내는 순서가 다르면 다른 방법으로 셉니다. 같은 표라도 칸의 뜻이 달라지면 반복의 순서가 답을 바꾼다는 것을 보여 주는 예입니다.

정리

• 동적 계획법은 겹치는 작은 문제의 답을 표에 저장해 다시 계산하지 않는 설계 방법입니다. 모든 경우를 따지는 재귀는 같은 금액을 여러 번 풀어 호출이 폭발적으로 늘어납니다.
• 상태 best[x]를 "금액 x를 만드는 최소 동전 개수"로 정하고, 마지막 동전을 기준으로 best[x] = min(best[x - c] + 1)이라는 점화식을 세웁니다.
• 각 칸은 더 작은 금액의 칸만 읽으므로 금액 0부터 차례로 채우고, 고른 마지막 동전을 기록해 두었다가 거꾸로 따라가 구성을 복원합니다.
• 최적의 답에서 마지막 동전을 뺀 나머지도 최적이라는 최적 부분 구조가 점화식이 맞는 이유입니다.
• 시간은 O(AC), 공간은 O(A)이며, 금액 자체에 비례하는 의사 다항 시간이라 금액이 매우 크면 쓸 수 없습니다.

연습 문제

1. 탐욕법과 동적 계획법 비교하기

동전 [5, 4, 1]로 금액 8을 만들 때, 큰 동전부터 고르는 탐욕법의 결과와 동적 계획법의 결과를 비교하세요.

2. 동전 0을 허용하면

동전 목록에 0이 들어 있으면 점화식과 계산 순서에 어떤 문제가 생길까요? 본문의 함수가 동전 0을 거절하지 않는다면 결과는 어떻게 될지도 생각해 보세요.

3. 만들 수 없는 금액

동전 [4, 6]으로 만들 수 없는 금액을 10 이하에서 모두 찾고, 그 금액들에서 best가 어떤 값으로 남는지 설명하세요.

다음 글 피보나치의 메모이제이션과 반복에서는 같은 동적 계획법을 위에서부터 필요한 칸만 저장하며 계산하는 방법과 아래에서부터 표를 채우는 방법으로 나누어 비교합니다.