동적계획법(DP) 입문: 점화식부터 코딩테스트 적용까지

동적계획법(Dynamic Programming, DP)은 코딩테스트에서 가장 어렵게 느껴지지만, 한 번 감을 잡으면 점수를 크게 끌어올리는 분야입니다. 핵심은 단 하나, 한 번 푼 문제는 다시 풀지 않는다입니다.

DP를 쓸 수 있는 조건

아무 문제에나 DP를 쓸 수 있는 건 아닙니다. 두 가지 조건을 만족해야 합니다.

• 중복 부분 문제(Overlapping Subproblems): 같은 작은 문제가 여러 번 반복해서 등장한다
• 최적 부분 구조(Optimal Substructure): 작은 문제의 최적해를 모으면 큰 문제의 최적해가 된다

이 둘이 보이면 "DP 각"입니다. 그다음 할 일은 **점화식(작은 문제와 큰 문제의 관계식)**을 세우는 것입니다.

메모이제이션 vs 타뷸레이션

DP 구현 방식은 크게 두 가지입니다.

구분	메모이제이션	타뷸레이션
방향	위→아래 (재귀)	아래→위 (반복문)
방식	필요한 값만 계산·캐싱	작은 값부터 표를 채움
장점	직관적, 필요한 부분만	스택 오버플로 없음, 빠름
단점	재귀 깊으면 위험	모든 상태를 다 계산

예시 1: 피보나치로 보는 점화식

피보나치는 f(n) = f(n-1) + f(n-2)라는 점화식을 그대로 코드로 옮기면 됩니다. 단순 재귀는 같은 값을 수없이 다시 계산해 O(2ⁿ)이지만, 표에 저장하면 **O(n)**이 됩니다.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 점화식 그대로
    return dp[n]

print([fib(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

예시 2: 0/1 배낭 문제

무게 한도 W 안에서 가치 합을 최대로 만드는 고전 DP입니다. 상태를 dp[i][w] = "i번째까지 고려, 무게 한도 w일 때 최대 가치"로 정의합니다. 각 물건을 담을지 말지 선택하는 게 핵심입니다.

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                 # 안 담는 경우
            if weights[i - 1] <= w:                 # 담을 수 있으면
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  # 담는 경우
                )
    return dp[n][W]

print(knapsack(7, [1, 3, 4, 5], [1, 4, 5, 7]))  # 9

함정: DP는 "상태 정의"가 8할입니다. dp[i]가 정확히 무엇을 의미하는지 한 문장으로 말할 수 없다면 점화식도 틀립니다. 코드부터 짜지 말고 상태 정의 → 점화식 → 초기값 순서로 접근하세요.

마무리 체크리스트

• 중복 부분 문제 + 최적 부분 구조가 보이는가?
• dp[i]의 의미를 한 문장으로 정의했는가?
• 점화식과 초기값(base case)을 세웠는가?
• 재귀가 깊으면 메모이제이션 대신 타뷸레이션을 고려했는가?

DP는 암기가 아니라 유형 반복 훈련입니다. 피보나치 → 계단 오르기 → 배낭 → LCS(최장 공통 부분 수열) 순으로 점화식 세우는 연습을 쌓으면 어느 순간 "DP 각"이 보입니다.