동적 계획법 입문 (DP)

DP가 필요한 순간

1. 최적 부분 구조: 큰 문제의 최적해가 작은 문제의 최적해로 설명됨
2. 중복 부분 문제: 같은 작은 문제를 여러 번 품

탐욕이 안 되고, 재귀만 하면 지수 시간이 날 때 DP를 의심하세요.

사고 순서 (중요)

1. 상태 정의: dp[i] = … 가 무엇을 의미하는가 (한 문장)
2. 점화식: dp[i]를 이전 상태들로 어떻게 쓰는가
3. 기저: dp[0] / dp[1] 등
4. 순회 순서: 의존하는 칸을 먼저 계산
5. 답의 위치: dp[n]인지 max(dp)인지

상태 정의가 흐리면 점화식이 영원히 안 나옵니다.

예 1: 피보나치 (메모이제이션 → 테이블)

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]

재귀만 하면 같은 fib(k)를 폭발적으로 다시 계산합니다. 테이블은 O(n).

예 2: 1차원 배낭·계단 (개념)

dp[i] = i에 도달하는 방법 수 또는 i까지 최소 비용처럼 인덱스 = 진행도로 두는 경우가 많습니다.

// 계단: 한 번에 1 또는 2칸
function climb(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

공간을 O(1)로 줄인 형태입니다. 처음엔 O(n) 배열로 명확히 쓰세요.

Top-down vs Bottom-up

이 사이트에서는 콜스택 한도를 고려해 bottom-up을 우선 권합니다.

함정

• 상태를 너무 많이 넣음 (차원이 폭증)
• 점화식에서 중복 계산·누락 전이
• 모듈로 나눗셈 문제에서 빼기 순서
• “DP인 줄 알았는데 그리디/투포인터”인 경우 · 연속 구간이면 슬라이딩을 먼저 의

학습 경로

1. 피보나치·계단·집 털기(1열)
2. 그리드 경로 수 (2차원)
3. LCS / 배낭은 그다음

한 문제를 상태 한 문장으로 말해 보고, 안 되면 정의를 고치세요. 코드는 그다음입니다.

복잡도

상태 수 × 전이 비용.
상태 O(n), 전이 O(1)이면 O(n)입니다.