동적 계획법, DP(Dynamic Programing)란?

DP란?

하나의 큰 문제를 작은 문제로 나누어 해결하고 그 결과를 저장해두었다가 재 사용하는 알고리즘 기법이다.

핵심

• 부분 문제로 분할 : 원래 문제를 더 작은, 같은 형태의 문제로 쪼갤 수 있음
• 결과 저장 : 한 번 계산한 건 다시 계산하지 않음

DP 사용 이유

같은 계산을 반복하지 않기 위해서
대표적 예시 : 피보나치 수열
-> 재귀로 계산하면 시간복잡도가 O(n^2)이지만
DP로 풀면 O(n)으로 확 줄어든다.

DP 사용 조건

1. 최적 부분 구조

큰 문제의 최적해가 작은 부분 문제들의 최적해로 구성될 수 있어야 한다.
ex) "1번~10번 계단을 오르는 최소 비용" = "1번~9번 최소 비용" + "9번→10번 비용"

2. 중복되는 부분 문제

같은 부분 문제가 여러 번 등장해야 한다.

이 두 조건이 모두 맞으면 DP가 가능하다.

DP 사용 사례

• 피보나치 / 계단 오르기 — 1칸 또는 2칸씩 오를 때 경우의 수
• 최장 증가 부분 수열 (LIS)
• 배낭 문제 (Knapsack) — 무게 제한 내 최대 가치 담기
• 동전 교환 문제 — 최소 동전 개수로 특정 금액 만들기
• 편집 거리 (Edit Distance) — 두 문자열을 같게 만드는 최소 연산 수
• 최장 공통 부분 수열 (LCS)

문제를 볼 때 "이전 상태를 기반으로 다음 상태가 결정되는가?"를 먼저 생각해보면 DP인지 감이 온다.

DP 구현 방법

1. 탑다운 방식 = 메모이제이션

재귀로 큰 문제부터 내려가되, 계산한 값은 저장해두기.

const memo = {};

function fib(n) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n]; // 저장된 값 재사용
  
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

장점: 직관적. 필요한 값만 계산.
단점: 재귀 스택 오버플로우 위험.

2. 바텀업 방식 = 타뷸레이션

작은 문제부터 차례로 풀어서 배열에 채워나가기.

function fib(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

장점: 반복문이라 스택 안전. 보통 더 빠름.
단점: 불필요한 값도 계산할 수 있음.

DP 문제를 푸는 사고 순서

1. 문제를 작은 문제로 쪼갤 수 있는가? 확인

2. 상태 정의 — dp[i]가 뭘 의미하는지 명확히 정하기
   예: dp[i] = "i번째까지 올라가는 최소 비용"

3. 점화식 세우기 — dp[i]를 dp[i-1], dp[i-2] 등으로 표현
   예: dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

4. 초기값 설정 — dp[0], dp[1] 같은 베이스 케이스

5. 구현 — 탑다운이든 바텀업이든 점화식대로 코드 작성