개념

동적 계획법(Dynamic Programming, DP)은 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 한 번만 풀어 답을 저장해 두었다가 같은 부분 문제가 다시 나오면 저장한 답을 꺼내 쓰는 방법입니다. 1950년대에 리처드 벨먼(Richard Bellman)이 정리한 방법으로, 여기서 "programming"은 코드 작성이 아니라 표를 채워 가며 계획을 세운다는 뜻입니다. 이 장에서는 DP가 언제 통하는지, 그 바탕이 되는 두 가지 성질, 그리고 이후 장에서 쓰는 용어를 정리합니다.

DP가 성립하는 두 가지 성질

문제가 다음 두 성질을 모두 가지면 DP로 풀기 좋습니다.

• 겹치는 부분 문제(overlapping subproblems): 단순한 재귀 풀이가 같은 부분 문제를 여러 번 풉니다. 결과를 저장해 두면 반복 계산이 표 조회 한 번으로 바뀝니다.
• 최적 부분 구조(optimal substructure): 전체 문제의 최적 해를 부분 문제의 최적 해로 조립할 수 있습니다. 예를 들어 B를 거쳐 A에서 C로 가는 최단 경로에는 A에서 B까지의 최단 경로가 들어 있습니다.

분할 정복도 문제를 부분 문제로 나누지만, 병합 정렬의 두 절반은 서로 겹치지 않으므로 다시 쓸 답이 없습니다. 그리디 알고리즘도 최적 부분 구조에 기대지만 매 단계에서 당장 가장 좋아 보이는 선택 하나만 확정합니다. DP는 가능한 선택을 모두 따져 보고 가장 좋은 것을 고르기 때문에 그리디가 틀리는 문제에서도 정확한 답을 냅니다.

겹침을 눈으로 확인하기: 피보나치

피보나치 수는 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)로 정의됩니다. 정의를 그대로 코드로 옮기면 답은 맞지만, 같은 값을 계속 다시 계산하므로 매우 느립니다.

calls = 0


def fib(n: int) -> int:
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(25), calls)  # 75025 242785

F(25) 하나를 구하는 데 함수가 약 24만 번 호출되고, 호출 수는 대략 1.6^n의 속도로 늘어납니다. 그런데 서로 다른 부분 문제는 F(0)부터 F(25)까지 26개뿐입니다. "실제 호출 수"와 "서로 다른 부분 문제 수" 사이의 이 차이를 없애는 것이 DP입니다.

답을 기억하는 두 가지 방법

메모이제이션(memoization, 하향식)은 재귀 구조를 그대로 두고 캐시를 붙입니다. 어떤 인자로 처음 호출되면 계산하고, 그 뒤에는 저장된 값을 돌려줍니다. Python에서는 functools.cache 데코레이터 하나로 됩니다.

from functools import cache


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


print(fib(90))           # 2880067194370816120
print(fib.cache_info())  # CacheInfo(hits=88, misses=91, maxsize=None, currsize=91)

타뷸레이션(tabulation, 상향식)은 재귀를 아예 쓰지 않습니다. 각 부분 문제가 의존하는 값이 항상 먼저 계산되는 순서를 정하고, 그 순서대로 반복문으로 표를 채웁니다.

def fib(n: int) -> int:
    table = [0] * (n + 1)
    if n > 0:
        table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(fib(90))  # 2880067194370816120

두 방식 모두 n + 1개의 값을 한 번씩만 계산하므로 시간은 O(n)입니다. 메모이제이션은 보통 작성이 더 빠르고, 시작 상태에서 실제로 도달하는 상태만 계산합니다. 타뷸레이션은 재귀 깊이 제한과 함수 호출 비용이 없고, 메모리를 줄이는 최적화가 눈에 잘 보입니다.

용어 정리

언제 DP를 떠올릴까

문제가 다음 중 하나를 묻고, 상태 표가 메모리에 들어갈 만큼 입력이 작다면 DP를 먼저 검토합니다.

• 최솟값이나 최댓값: 가장 적은 동전 수, 가장 싼 경로, 가방에 담을 수 있는 최대 가치
• 경우의 수: 격자 경로의 수, 계단을 오르는 방법의 수, 문자열을 해석하는 방법의 수
• 가능 여부: 집합을 합이 같은 두 묶음으로 나눌 수 있는지, 문자열을 사전 단어로 쪼갤 수 있는지

풀이가 선택을 차례로 내리는 모양이고, 선택 하나를 내린 뒤 남은 문제가 원래 문제의 작은 판처럼 보인다면 강한 신호입니다. 서로 다른 선택 순서가 같은 남은 문제로 이어진다면 부분 문제가 겹친다는 뜻입니다. 코딩 테스트에서 "방법의 수를 1,000,000,007로 나눈 나머지" 같은 문구가 보이면 거의 항상 DP 문제입니다.

정리

• DP는 서로 다른 부분 문제를 한 번씩만 풀고 저장한 답을 다시 씁니다.
• 겹치는 부분 문제와 최적 부분 구조가 있어야 합니다.
• 메모이제이션은 재귀에 캐시를 붙이고, 타뷸레이션은 의존 순서대로 표를 채웁니다.
• 모든 DP 풀이는 상태, 점화식, 기저 사례, 계산 순서, 최종 답으로 설명할 수 있습니다.