동적 계획법(DP) 쉽게 이해하기: 동작 원리, 코드, 예제

동적 계획법이 해결하는 문제

최선, 최저 비용, 경우의 수를 묻는 문제가 많습니다. 금액을 만드는 최소 동전 수, 두 문자열의 최장 공통 부분 수열, 가방에 들어가는 가장 가치 있는 물건 조합, 격자를 지나는 경로의 수가 그 예입니다. 직접 재귀로 풀면 같은 작은 경우를 지수적으로 여러 번 다시 계산하는 일이 흔합니다. DP는 이 반복을 없앱니다.

이름은 1950년대에 이 방법을 개발한 리처드 벨먼(Richard Bellman)에서 왔습니다. 여기서 "프로그래밍"은 코드를 작성한다는 뜻이 아니라 계획을 세우거나 표를 채운다는 뜻입니다.

핵심 아이디어

단순 재귀 피보나치가 문제를 보여 줍니다. fib(5)는 fib(4)와 fib(3)을 호출하고, fib(4)는 다시 fib(3)을 호출하는 식이어서 호출 횟수가 지수적으로 늘어납니다. 각 결과를 처음 계산할 때 저장해 두면 이후의 호출은 즉시 끝납니다.

1. 상태를 정의합니다. 부분 문제는 어떤 모양일까요? 예를 들어 best[a] = 금액 a를 만드는 최소 동전 수입니다.
2. 점화식을 씁니다. 더 작은 상태로부터 어떻게 한 상태를 계산할까요? best[a] = 1 + min(best[a - c] for each coin c).
3. 기저 사례를 정합니다. best[0] = 0.
4. 순서를 정합니다. 메모이제이션을 쓰는 하향식으로 하거나, 더 작은 상태가 항상 먼저 채워지도록 상향식으로 합니다.
5. 알맞은 상태에서 답을 읽고, 필요하면 실제 선택도 복원합니다.

하향식: functools를 이용한 메모이제이션

파이썬에서는 functools.cache(파이썬 3.9 이상) 또는 functools.lru_cache로 한 줄만 더하면 함수에 메모이제이션이 적용됩니다.

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

데코레이터가 없으면 fib(80)은 10¹⁶번이 넘는 재귀 호출을 하게 됩니다. 데코레이터가 있으면 0부터 80까지의 각 값을 한 번씩만 계산합니다.

예제: 상향식 동전 거스름돈

동전 1, 3, 4로 금액 6을 만듭니다. 그리디 방식은 4를 먼저 집어 4 + 1 + 1 = 3개가 필요하지만 3 + 3은 2개면 됩니다. DP는 a = 0부터 6까지 best[a]를 채워 진짜 최솟값을 찾습니다.

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

2차원 예제: 최장 공통 부분 수열

두 시퀀스에 대한 많은 DP 문제는 격자를 사용합니다. dp[i][j]는 한 문자열의 앞 i개 문자와 다른 문자열의 앞 j개 문자에 대한 답입니다. 최장 공통 부분 수열(LCS)에서는 문자가 같으면 대각선 값을 확장하고, 다르면 어느 한 문자열에서 문자 하나를 빼는 두 경우 중 더 좋은 쪽을 택합니다.

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

길이 4인 LCS의 하나는 BCBA입니다. 같은 표 구조로 편집 거리를 풀 수 있으며, 텍스트 diff 도구가 두 문자열이 얼마나 다른지 측정하는 방법이 바로 이것입니다.

시간 복잡도와 공간 복잡도

일반 규칙: 시간 = 상태 수 × 상태당 작업량, 공간 = 저장하는 상태 수.

배낭 문제의 O(n × W)는 의사 다항 시간입니다. 입력의 비트 크기가 아니라 숫자 값 W에 의존하므로 W가 매우 크면 느립니다.

흔한 실수와 DP를 쓰는 경우

• 잘못된 상태: 점화식이 상태에 담기지 않은 정보(예를 들어 이미 사용한 물건)를 필요로 하면 답이 틀립니다. 그 정보를 상태에 추가하세요.
• 잘못된 채우기 순서: 상향식 반복문은 어떤 상태를 읽기 전에 그 상태를 먼저 계산해야 합니다.
• 표 크기의 off-by-one: 길이가 n인 문자열은 빈 접두사까지 포함하려면 n + 1개의 행이 필요합니다.
• 깊은 재귀: 상태가 10,000개인 메모이제이션 재귀는 파이썬의 재귀 한도를 넘을 수 있습니다. 상향식으로 바꾸세요.
• 해시 불가능한 인자: functools.cache는 해시 가능한 인자가 필요하므로 리스트 대신 튜플을 넘기세요.

대표적인 코딩 인터뷰 문제와 실제 활용: 계단 오르기, 집 털이범, 최장 증가 부분 수열, 단어 나누기, 격자의 고유 경로, 편집 거리, 배낭 문제, 행렬 체인 곱셈. 실무에서는 생물정보학의 서열 정렬, diff 도구, 맞춤법 검사기, 음성 인식(비터비 알고리즘), 벨만-포드 같은 최단 경로에 쓰입니다.