6 / 16강

계산 결과를 기억하는 동적 계획법

1, 3, 4원 동전으로 6원을 만드는 최소 동전 수를 구해 봅시다. 탐욕법은 3개를 골랐지만 정답은 2개였습니다. 작은 금액의 정답을 기억하면 가능한 마지막 동전을 빠짐없이 비교할 수 있습니다.

세 가지부터 적습니다

• 상태: dp[x]는 금액 x를 만드는 최소 동전 수입니다.
• 시작값: dp[0] = 0입니다. 0원에는 동전이 필요 없습니다.
• 점화식: 마지막 동전이 c라면 후보는 dp[x-c] + 1입니다. 가능한 동전마다 비교해 최솟값을 고릅니다.

금액이 작은 상태부터 채우면 필요한 이전 값이 이미 계산되어 있습니다. 만들 수 없는 금액은 무한대로 남겨 둡니다. 동전의 종류는 양의 정수이며 각각 무제한 사용할 수 있다고 가정합니다.

coins = [1, 3, 4]
amount = 6
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for value in range(1, amount + 1):
    for coin in coins:
        if coin <= value:
            dp[value] = min(dp[value], dp[value - coin] + 1)
print(dp[amount])

출력은 2입니다. 6원의 후보는 1원 동전을 더한 dp[5]+1, 3원을 더한 dp[3]+1, 4원을 더한 dp[2]+1입니다. 그중 dp[3]+1 = 2가 가장 작습니다.

재귀와 무엇이 다를까요?

동적 계획법(DP)은 구현 문법보다 같은 상태를 다시 계산하지 않는 설계를 가리킵니다. 재귀로 필요할 때 계산해 저장하는 메모이제이션과, 작은 상태부터 표를 채우는 타뷸레이션이 있습니다. 위 코드는 후자입니다.

상태를 나눈 뒤에도 최적해를 만들 수 있어야 하고, 반복해서 만나는 상태의 답을 재사용할 수 있어야 합니다. 모든 재귀 문제가 자동으로 효율적인 DP가 되는 것은 아닙니다.

목표 금액이 A, 동전 종류가 k개면 시간은 O(Ak), 공간은 O(A)입니다. 금액이 아주 크면 이 표 자체가 부담이 됩니다.

확인 문제

동전이 2원과 4원뿐인데 3원을 만들라고 하면 어떻게 표시해야 할까요? dp[0]을 무한대로 두면 어떤 문제가 생길까요?