Dynamic Programming

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누고, 같은 계산을 반복하지 않도록 저장하면서 푸는 기법이다.

한 줄로 요약하면 다음과 같다.

작은 문제의 답을 저장해 두고
그 답으로 큰 문제를 만든다

---

1. DP는 언제 쓰는가

문제에서 아래 느낌이 나면 DP를 의심하면 된다.

• 경우의 수 최댓값 / 최솟값
• i번째까지 봤을 때의 최적해
• 선택 / 비선택
• 이전 상태에 따라 현재 답이 결정됨
• 같은 부분 문제가 반복됨
• 완전탐색은 되지만 너무 느림

대표 예시:

• 피보나치 수열
• 계단 오르기
• 배낭 문제
• LIS, LCS
• 문자열 편집 거리
• 트리 DP
• 비트마스크 DP

---

2. DP의 본질

DP의 핵심은 두 가지다.

1) 부분 문제 중복 Overlapping Subproblems

같은 작은 문제를 여러 번 계산하게 된다.

예:

f(5)를 구할 때 f(4), f(3)이 필요하고
f(4)를 구할 때 또 f(3), f(2)가 필요하다

즉 f(3) 같은 계산이 반복된다.

2) 최적 부분 구조 Optimal Substructure

큰 문제의 최적해가 작은 문제의 최적해로부터 만들어진다.

예:

i번째까지의 최댓값은
(i-1)번째까지의 최댓값을 바탕으로 만든다

이 두 조건이 잘 맞으면 DP가 강력하다.

---

3. 왜 DP가 필요한가

완전탐색으로 모든 경우를 보려면 지수 시간이 걸리는 문제들이 많다.

하지만 작은 문제의 답을 저장하면, 같은 계산을 다시 하지 않아도 된다.

예를 들어 피보나치를 단순 재귀로 풀면 매우 느리다.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

이 방식은 fib(3), fib(2) 등을 계속 다시 계산한다.

flowchart TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4 --> F3b["fib(3)"]
    F4 --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]

위 그림을 보면 fib(3)이 두 번, fib(2)가 세 번 호출되는 것이 보인다. n이 커지면 이런 중복 호출이 기하급수적으로 늘어난다.

반면 DP로 저장하면 각 값은 한 번만 계산한다.

---

4. DP를 푸는 사고 순서

DP 문제를 풀 때는 아래 순서가 가장 중요하다.

1. dp[state]가 무엇을 의미하는가?
2. 점화식은 무엇인가?
3. 초기값은 무엇인가?
4. 어떤 순서로 계산해야 하는가?
5. 최종 답은 어디에 있는가?

이 다섯 개가 정리되면 구현은 대부분 자연스럽게 따라온다.

flowchart TD
    A["상태 정의"] --> B["점화식 작성"]
    B --> C["Base case 설정"]
    C --> D["채우기 순서 결정"]
    D --> E["테이블 채우기 또는 Memoization"]
    E --> F["최종 답 읽기"]

DP는 결국 이 순서대로 정리하는 작업이다. 코드보다 먼저 이 흐름이 머릿속에서 정리되어야 점화식이 흔들리지 않는다.

---

5. 상태 정의가 가장 중요하다

DP에서 가장 어려운 것은 코드가 아니라 상태 정의다.

예를 들어 계단 오르기 문제라면:

dp[i] = i번째 계단까지 왔을 때의 최대 점수

로 정의할 수 있다.

배낭 문제라면:

dp[i][w] = 앞에서 i개 물건만 고려했을 때
           무게 한도 w에서 얻을 수 있는 최대 가치

이처럼 상태는 다음을 담아야 한다.

• 지금 어디까지 왔는가
• 무엇을 알고 있는가
• 무엇이 답을 결정하는가

상태 정의가 잘못되면 점화식도 꼬인다.

---

6. 점화식이란 무엇인가

점화식은 현재 상태를 더 작은 상태들로 표현한 식이다.

예:

dp[i] = max(dp[i - 1], dp[i - 2] + value[i])

이 식은 현재 답이 이전 답들로부터 만들어진다는 뜻이다.

DP의 본질은 사실상 이 한 문장이다.

현재 답을 이전에 계산한 답들로 만든다

---

7. 초기값 Base Case

점화식만 있다고 끝이 아니다. 초기값이 반드시 필요하다.

예를 들어 피보나치:

dp[0] = 0
dp[1] = 1

배낭 문제:

dp[0][w] = 0

초기값은 DP의 출발점이다. 이걸 잘못 두면 전체가 틀린다.

---

8. Top-Down과 Bottom-Up

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

1) Top-Down 메모이제이션

재귀로 문제를 풀되, 이미 계산한 값은 저장해 두고 다시 계산하지 않는다.

int[] memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

장점:

• 점화식 그대로 쓰기 쉬움
• 문제 구조를 재귀적으로 보기 좋음

단점:

• 재귀 호출 오버헤드
• 스택 깊이 문제 가능

2) Bottom-Up 테이블 채우기

작은 상태부터 차례대로 채운다.

int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

장점:

• 반복문이라 안정적
• 계산 순서가 명확함

실전에서는 보통 Bottom-Up을 더 많이 쓴다.

---

9. 가장 기본 예제: 피보나치

정의:

dp[i] = i번째 피보나치 수

점화식:

dp[i] = dp[i - 1] + dp[i - 2]

초기값:

dp[0] = 0
dp[1] = 1

int fib(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

이 문제는 DP의 가장 순수한 입문형이다.

---

10. 1차원 DP의 대표 패턴

다음과 같은 문제는 1차원 DP인 경우가 많다.

• i번째까지 왔을 때의 최댓값
• i번째까지 고려했을 때의 경우의 수
• 앞에서부터 차례로 결정하는 문제

대표 예시:

• 계단 오르기
• 집 털기 House Robber
• 동전 교환
• 연속합

즉 축이 하나면 보통 dp[i] 형태를 먼저 생각하면 된다.

---

11. 선택 / 비선택 패턴

DP에서 가장 많이 나오는 사고다.

예를 들어 어떤 원소를 고를지 말지 결정하는 문제라면, 현재 선택이 이전 상태에 어떤 영향을 주는지만 보면 된다.

예시:

i번째 원소를 고른다 / 안 고른다

이 패턴은 다음 문제에 자주 나온다.

• 집 털기
• 계단 문제
• 배낭 문제
• 트리 독립 집합

---

12. 최대값 / 최소값 DP 예시: House Robber 형태

문제:

인접한 두 칸을 동시에 선택할 수 없을 때 최대 합

정의:

dp[i] = 0..i 구간에서 얻을 수 있는 최대 합

점화식:

dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])

왜냐하면:

• i를 안 고르면 dp[i - 1]
• i를 고르면 i - 1은 못 고르므로 dp[i - 2] + arr[i]

int solve(int[] arr) {
    int n = arr.length;
    if (n == 1) return arr[0];

    int[] dp = new int[n];
    dp[0] = arr[0];
    dp[1] = Math.max(arr[0], arr[1]);

    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
    }

    return dp[n - 1];
}

---

13. 경우의 수 DP 예시: 계단 오르기 수

문제:

한 번에 1칸 또는 2칸 오를 수 있을 때
n칸에 도달하는 방법 수

정의:

dp[i] = i칸에 도달하는 방법 수

점화식:

dp[i] = dp[i - 1] + dp[i - 2]

이유:

• 마지막에 1칸 올라왔다면 dp[i - 1]
• 마지막에 2칸 올라왔다면 dp[i - 2]

즉 경우의 수 DP도 결국 상태 정의와 점화식의 문제다.

---

14. 2차원 DP는 언제 나오는가

상태를 하나의 축으로 표현하기 부족할 때 2차원 DP가 나온다.

예:

• 몇 번째 원소까지 봤는가
• 현재 용량은 얼마인가
• 문자열의 어디까지 비교했는가
• 좌표 (i, j)에 도달했는가

대표 예시:

• 배낭 문제
• LCS
• 격자 경로 문제

---

15. 배낭 문제 0/1 Knapsack

문제:

각 물건은 한 번만 고를 수 있을 때
무게 제한 W 안에서 최대 가치를 구하라

정의:

dp[i][w] = 앞의 i개 물건만 고려했을 때
           무게 한도 w에서 얻을 수 있는 최대 가치

여기서 i는 “고려한 물건 수”다. 즉 현재 비교하는 물건의 실제 배열 인덱스는 i - 1이다.

점화식:

• 앞에서 i개 물건 중 마지막 물건을 안 고름
• 앞에서 i개 물건 중 마지막 물건을 고름

즉:

dp[i][w] = max(
    dp[i - 1][w],
    dp[i - 1][w - weight[i - 1]] + value[i - 1]
)

int knapsack(int[] weight, int[] value, int n, int W) {
    int[][] dp = new int[n + 1][W + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weight[i - 1]) {
                dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }

    return dp[n][W];
}

이 문제는 “선택/비선택” DP의 대표다.

손 계산 예시

물건: (무게, 가치) = (2,3), (3,4), (4,5)   W=5

       w= 0  1  2  3  4  5
i=0       0  0  0  0  0  0
i=1(2,3)  0  0  3  3  3  3
i=2(3,4)  0  0  3  4  4  7
i=3(4,5)  0  0  3  4  5  7

dp[2][5]: 무게 2 + 무게 3 = 5 ≤ W → 가치 3+4 = 7 ✓
dp[3][5]: 물건3을 고르면 dp[2][1] + 5 = 5,
          안 고르면 dp[2][5] = 7 → 더 큰 7 유지

---

16. 문자열 DP 예시: LCS

LCS(Longest Common Subsequence)는 두 문자열의 최장 공통 부분 수열 길이를 구하는 문제다.

정의:

dp[i][j] = 첫 문자열 앞 i개,
           둘째 문자열 앞 j개를 봤을 때의 LCS 길이

점화식:

• 문자가 같으면 대각선에서 +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])

점화식 증명

Case 1: a[i-1] == b[j-1] 일 때

두 문자열의 현재 끝 문자가 같다. 이 문자는 반드시 LCS에 포함시킬 수 있다.

귀류법:
이 문자를 포함하지 않는 더 긴 공통 부분 수열 L이 있다고 가정하자.
L은 a의 앞 i개, b의 앞 j개 안에서 만들어졌으므로
길이가 dp[i-1][j-1] + 1보다 클 수 없다.
왜냐하면 a[i-1]과 b[j-1]을 빼면 남는 범위가 a의 앞 i-1개, b의 앞 j-1개이고
그 범위의 LCS 최대 길이가 dp[i-1][j-1]이기 때문이다.
따라서 dp[i][j] = dp[i-1][j-1] + 1이 최적이다.

Case 2: a[i-1] != b[j-1] 일 때

두 끝 문자가 다르므로 둘 다 동시에 LCS의 마지막이 될 수 없다. 따라서 LCS는 다음 두 경우 중 하나에 반드시 속한다.

경우 A: a[i-1]이 LCS에 포함되지 않음 → LCS는 a의 앞 i-1개와 b의 앞 j개로 결정
경우 B: b[j-1]이 LCS에 포함되지 않음 → LCS는 a의 앞 i개와 b의 앞 j-1개로 결정

두 경우가 모든 가능성을 빠짐없이 커버하므로
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

이 문제는 “두 축을 동시에 따라가며 비교”하는 DP의 대표다.

손 계산 예시

a = "ABCB",  b = "BDCB"

       ""  B  D  C  B
  ""    0  0  0  0  0
   A    0  0  0  0  0
   B    0  1  1  1  1
   C    0  1  1  2  2
   B    0  1  1  2  3

a[1]='B' == b[0]='B' → dp[2][1] = dp[1][0] + 1 = 1 (최초 매치)
a[2]='C' == b[2]='C' → dp[3][3] = dp[2][2] + 1 = 1+1 = 2
a[3]='B' == b[3]='B' → dp[4][4] = dp[3][3] + 1 = 2+1 = 3

LCS = "BCB", 길이 3

---

17. LIS 최장 증가 부분 수열

LIS는 수열 DP의 대표 문제다.

O(N^2) DP 정의

dp[i] = i에서 끝나는 LIS 길이

점화식:

arr[j] < arr[i] 이면
 dp[i] = max(dp[i], dp[j] + 1)

점화식 증명

dp[i]는 arr[i]를 마지막 원소로 하는 LIS의 길이다.

1. 초기값: dp[i] = 1
   원소 하나만으로도 길이 1인 증가 수열이 된다.

2. 전이: j < i이고 arr[j] < arr[i]인 모든 j에 대해
   dp[i] = max(dp[i], dp[j] + 1)

왜 이것이 성립하는가?

arr[i]로 끝나는 LIS를 생각하면
그 직전 원소는 반드시 arr[i]보다 작고 인덱스가 i보다 앞이다.

직전 원소가 arr[j]라면
arr[j]로 끝나는 LIS 뒤에 arr[i]를 붙인 것이므로
길이는 dp[j] + 1이 된다.

가능한 모든 j 중 dp[j]가 가장 큰 것을 택하면
arr[i]로 끝나는 가장 긴 증가 수열을 얻는다.

최종 답이 max(dp[i])인 이유:

LIS가 어떤 인덱스에서 끝날지 모르므로
모든 위치에서 끝나는 LIS 중 최댓값이 전체 LIS 길이다.

int lis(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

LIS는 나중에 O(N log N) 최적화도 배우게 되지만, 처음에는 DP 관점으로 이해하는 것이 중요하다.

O(N log N) 방식 요약: tails 배열을 유지하면서, 새 원소가 tails 끝보다 크면 추가, 아니면 이진 탐색으로 대체할 위치를 찾는다. tails.length가 LIS 길이가 된다. N이 크면(10만 이상) 이 방식이 필수다.

---

18. 점화식이 안 보일 때 질문해야 할 것

DP가 막힐 때는 아래를 스스로 물어보면 된다.

1. 마지막 행동은 무엇이었는가?
2. 현재 상태를 결정하는 최소 정보는 무엇인가?
3. 현재를 만들 수 있는 직전 상태는 무엇인가?
4. 중복 계산이 생기는가?
5. 답을 표로 저장할 수 있는가?

특히 “마지막 행동”을 생각하는 것이 매우 강력하다.

예:

• 마지막에 물건을 골랐는가?
• 마지막 문자가 같은가?
• 마지막 계단을 어떻게 왔는가?

---

19. 메모리 최적화

어떤 DP는 전체 테이블이 필요 없다. 오직 직전 상태만 필요할 때는 공간을 줄일 수 있다.

예:

피보나치:

int fib(int n) {
    if (n <= 1) return n;

    int a = 0;
    int b = 1;

    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }

    return b;
}

즉 상태 전이가 오직 몇 개의 이전 값에만 의존하면, 배열 전체를 들고 있을 필요가 없다.

배낭 문제의 메모리 최적화: 토글링

0/1 배낭의 2차원 DP를 다시 보면:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i - 1]] + value[i - 1])

i번째 행을 채울 때 참조하는 것은 오직 i-1번째 행뿐이다. 즉 전체 n개 행이 아니라 이전 행 하나만 있으면 된다.

방법 1: 두 줄 토글링

행 두 개만 번갈아 쓰는 방식이다.

int knapsack(int[] weight, int[] value, int n, int W) {
    int[][] dp = new int[2][W + 1];

    for (int i = 1; i <= n; i++) {
        int cur = i % 2;
        int prev = (i - 1) % 2;
        for (int w = 0; w <= W; w++) {
            dp[cur][w] = dp[prev][w];
            if (w >= weight[i - 1]) {
                dp[cur][w] = Math.max(dp[cur][w], dp[prev][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }

    return dp[n % 2][W];
}

공간이 O(N × W)에서 O(2 × W) = O(W)로 줄어든다.

방법 2: 1차원 배열 + 역순 순회

한 줄로 더 줄일 수 있다. 핵심은 w를 큰 쪽에서 작은 쪽으로 순회하는 것이다.

int knapsack(int[] weight, int[] value, int n, int W) {
    int[] dp = new int[W + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = W; w >= weight[i - 1]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weight[i - 1]] + value[i - 1]);
        }
    }

    return dp[W];
}

왜 역순인가?

정순(w = 0 → W)으로 돌면
dp[w - weight[i - 1]]가 이미 현재 물건이 반영된 "현재 행" 값이다.
즉 같은 물건을 여러 번 고르는 셈이 된다.

역순(w = W → 0)으로 돌면
dp[w - weight[i - 1]]는 아직 갱신 전이므로 "이전 행" 값이다.
따라서 각 물건을 최대 한 번만 고르는 0/1 배낭이 유지된다.

참고: 물건을 여러 번 고를 수 있는 Unbounded Knapsack에서는 정순 순회가 맞다.

---

20. 역추적 Backtracking

DP로 최적값을 구한 뒤, 그 값을 만든 실제 선택을 복원하는 것이 역추적이다.

DP 테이블에는 “최적값”만 저장되어 있으므로, 어떤 선택이 그 값을 만들었는지 거꾸로 따라가야 한다.

핵심 아이디어:

1. DP 테이블을 먼저 다 채운다
2. 최종 답 위치에서 출발해 역방향으로 이동한다
3. 각 위치에서 "어떤 전이가 현재 값을 만들었는가"를 판단한다
4. 그 전이에 해당하는 선택을 기록한다

LCS 역추적

DP 테이블을 채운 뒤 (i, j) = (m, n)에서 출발한다.

String traceLCS(String a, String b, int[][] dp) {
    int i = a.length();
    int j = b.length();
    StringBuilder sb = new StringBuilder();

    while (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            sb.append(a.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return sb.reverse().toString();
}

동작 원리:
- 문자가 같으면: 이 문자는 LCS에 포함 → 기록하고 대각선 이동
- 다르면: dp[i-1][j]와 dp[i][j-1] 중 큰 쪽으로 이동
  (값이 줄어들지 않는 방향 = 선택이 발생하지 않은 방향)

0/1 배낭 역추적

어떤 물건을 골랐는지 복원한다.

List<Integer> traceKnapsack(int[][] dp, int[] weight, int[] value, int n, int W) {
    List<Integer> selected = new ArrayList<>();
    int w = W;

    for (int i = n; i >= 1; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            selected.add(i - 1);
            w -= weight[i - 1];
        }
    }

    Collections.reverse(selected);
    return selected;
}

동작 원리:
- dp[i][w] != dp[i-1][w]이면
  배열 인덱스 i-1인 물건을 골랐다는 뜻이다.
  (안 골랐다면 값이 이전 행과 같아야 하므로)
- 골랐으면 잔여 용량에서 해당 무게를 빼고 다음 물건으로 이동한다.

LIS 역추적

List<Integer> traceLIS(int[] arr, int[] dp) {
    int n = arr.length;
    int maxLen = 0;
    int maxIdx = 0;

    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }

    List<Integer> result = new ArrayList<>();
    result.add(arr[maxIdx]);
    int curLen = maxLen;

    for (int i = maxIdx - 1; i >= 0; i--) {
        if (dp[i] == curLen - 1 && arr[i] < arr[maxIdx]) {
            result.add(arr[i]);
            curLen--;
            maxIdx = i;
        }
    }

    Collections.reverse(result);
    return result;
}

동작 원리:
- dp 값이 가장 큰 위치에서 출발한다.
- 뒤에서 앞으로 가면서 dp 값이 정확히 1 작고
  원소 값도 더 작은 위치를 찾아 이어 붙인다.

역추적의 일반 원칙

1. DP 테이블을 완성한 뒤에 수행한다
2. 최종 답 위치에서 시작해 역방향으로 이동한다
3. 각 칸에서 "이 값이 어디서 왔는가"만 확인한다
4. 별도 choice 배열을 두면 역추적이 더 간단해진다

팁: 역추적이 복잡할 때는 DP를 채우면서 choice[i][j]에 전이 방향을 미리 기록해 두면 역추적 코드가 훨씬 단순해진다.

---

21. 많은 DP는 Top-Down으로 시작하기 쉽다

Top-Down의 핵심은 이것이다.

많은 전형적 DP는
상태와 종료 조건을 정한 뒤
완전탐색에 memo를 붙여 구현할 수 있다

즉 Top-Down은 사실 DP를 푸는 것이 아니라 종종 완전탐색에 저장을 붙이는 방식으로 구현하는 것이다.

왜 점화식을 먼저 식으로 쓰지 않아도 되는가

Bottom-Up은 이런 흐름이다.

1. 상태를 정의한다
2. 점화식을 세운다
3. 채우기 순서를 설계한다
4. for문으로 테이블을 채운다

이 중 2번과 3번이 어렵다. 점화식이 안 보이거나, 순서가 꼬이면 막힌다.

Top-Down은 다르다.

1. "이 상태에서 할 수 있는 선택이 뭐가 있지?"만 생각한다
2. 각 선택을 재귀로 시도한다
3. 결과를 저장한다

점화식을 먼저 수식 형태로 적지 않아도 되는 경우가 많다. 다만 상태 정의, 종료 조건, 메모이제이션 기준은 여전히 정확해야 한다. 보통은 “지금 뭘 할 수 있는가”를 코드로 적다 보면 점화식이 자연스럽게 드러난다.

flowchart TD
    A["현재 상태에서 시작"] --> B{"끝난 상태인가?"}
    B -- 예 --> C["기저값 반환"]
    B -- 아니오 --> D{"이미 계산했는가?"}
    D -- 예 --> E["저장된 값 반환"]
    D -- 아니오 --> F["가능한 선택지를 모두 시도"]
    F --> G["각 선택의 결과 중 최적값 선택"]
    G --> H["결과를 memo에 저장"]
    H --> I["저장된 값 반환"]

3단계 접근: 완전탐색 → memo 추가 → 정리

많은 전형적 DP는 이 순서로 접근할 수 있다.

1단계: 완전탐색을 먼저 짠다

점화식 같은 건 잊고 그냥 모든 경우를 재귀로 탐색하는 코드를 짠다. “이 상태에서 할 수 있는 선택은 무엇인가?”만 생각한다.

2단계: memo 배열을 추가한다

같은 상태를 두 번 이상 계산하지 않도록 결과를 저장한다. 이것만으로 완전탐색이 DP가 된다.

3단계: 상태를 점검하고 정리한다

재귀가 필요한 순서를 자동으로 따라가므로 Bottom-Up처럼 채우기 순서를 직접 설계할 부담은 줄어든다. 다만 상태 정의나 기저 조건이 틀리면 Top-Down도 그대로 틀린다.

템플릿 코드

int[] memo; // 또는 int[][] memo

int solve(상태) {
    // 1. 끝난 상태면 바로 반환
    if (종료 조건) return 기저값;

    // 2. 이미 계산한 상태면 바로 반환
    if (memo[상태] != -1) return memo[상태];

    // 3. 할 수 있는 선택을 모두 시도
    int result = 초기값;
    for (각 선택지) {
        result = 비교(result, solve(선택 후 상태));
    }

    // 4. 저장하고 반환
    return memo[상태] = result;
}

주의: memo의 초기값으로 -1을 많이 쓰는데, 답이 -1일 수 있는 문제에서는 visited 배열을 별도로 두거나 Long.MIN_VALUE 같은 센티널을 쓴다.

예시 1: 피보나치

생각 과정:

Q: fib(n)을 구하려면?
A: fib(n-1)과 fib(n-2)를 더하면 된다.
Q: 언제 끝나는가?
A: n이 0이면 0, 1이면 1.

이게 전부다. 점화식을 세운 게 아니라 “어떻게 구하지?”를 자연어로 답한 것뿐이다.

int[] memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

예시 2: 0/1 배낭

생각 과정:

Q: 앞에서 i개 물건을 볼 수 있고 용량 w가 남았다. 뭘 할 수 있는가?
A: 두 가지.
   - 이 물건을 안 고른다 → solve(i-1, w)
   - 이 물건을 고른다 → solve(i-1, w-weight[i-1]) + value[i-1]
   둘 중 큰 값을 택한다.
Q: 언제 끝나는가?
A: 물건이 없으면 (i == 0) 가치는 0이다.

점화식을 세운 것이 아니다. “이 순간 무엇을 할 수 있는가?”에 답한 것뿐이다.

int[][] memo;
int[] weight, value;

int knapsack(int i, int w) {
    if (i == 0) return 0;
    if (memo[i][w] != -1) return memo[i][w];

    // 선택 1: 안 고른다
    int result = knapsack(i - 1, w);

    // 선택 2: 고른다 (용량이 되면)
    if (w >= weight[i - 1]) {
        result = Math.max(result, knapsack(i - 1, w - weight[i - 1]) + value[i - 1]);
    }

    return memo[i][w] = result;
}

예시 3: LCS

생각 과정:

Q: 문자열 a의 i번째, b의 j번째를 보고 있다. 뭘 할 수 있는가?
A: 두 문자가 같으면 → 이건 공통이다. 둘 다 한 칸 전진 + 1
   다르면 → a를 한 칸 버리거나, b를 한 칸 버리거나. 둘 중 큰 쪽.
Q: 언제 끝나는가?
A: 어느 한 쪽 문자열이 끝나면 0이다.

int[][] memo;
String a, b;

int lcs(int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];

    if (a.charAt(i - 1) == b.charAt(j - 1)) {
        return memo[i][j] = lcs(i - 1, j - 1) + 1;
    }
    return memo[i][j] = Math.max(lcs(i - 1, j), lcs(i, j - 1));
}

예시 4: LIS

생각 과정:

Q: arr[i]로 끝나는 가장 긴 증가 수열은?
A: i보다 앞에 있고 arr[j] < arr[i]인 모든 j에 대해
   "arr[j]로 끝나는 LIS 뒤에 arr[i]를 붙인다"를 시도한다.
   그 중 가장 긴 것을 택한다.
Q: 최소 길이는?
A: 자기 자신만으로 길이 1이다.

int[] memo;
int[] arr;

int lis(int i) {
    if (memo[i] != -1) return memo[i];

    int result = 1;  // 최소한 자기 자신
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            result = Math.max(result, lis(j) + 1);
        }
    }

    return memo[i] = result;
}

// 최종 답: 모든 i에 대해 max(lis(i))

정리: 완전탐색과 DP의 거리

flowchart LR
    A["완전탐색\n(재귀로 모든 경우 시도)"] -- "memo 추가" --> B["Top-Down DP"]
    B -- "재귀를 반복문으로" --> C["Bottom-Up DP"]

이 그림이 핵심이다.

• 완전탐색 → Top-Down: 같은 상태를 저장하는 memo를 붙이면 된다
• Top-Down → Bottom-Up: 점화식과 채우기 순서를 설계해야 한다

즉 Top-Down은 완전탐색에서 가장 가까운 DP다. 전형적인 문제에서는 상태와 선택만 명확해도 구현으로 옮기기 쉽다.

Bottom-Up과 Top-Down 비교

항목	Bottom-Up	Top-Down
사고 방식	점화식을 세우고 표를 채운다	선택지를 나열하고 재귀한다
채우기 순서	직접 설계해야 함	자동으로 결정됨
구현 난이도	점화식과 순서 둘 다 필요	완전탐색에 memo를 붙여 시작하기 쉬움
속도	보통 약간 빠름	재귀 오버헤드 있음
필요한 상태만 계산	모든 상태를 채움	호출된 상태만 계산
스택	안전	깊이 제한 주의

언제 Top-Down이 유리한가

1. 점화식이 바로 안 보일 때
   → "지금 뭘 할 수 있는가?"만 적으면 된다

2. 채우기 순서가 복잡하거나 비직관적일 때
   → 재귀가 알아서 필요한 순서를 찾아간다

3. 모든 상태를 채울 필요가 없을 때
   → 실제 호출되는 상태만 계산한다
   예: 트리 DP, 비트마스크 DP에서 도달 불가능한 상태가 많을 때

4. 빠르게 구현해야 할 때
   → 완전탐색 코드에 memo만 붙이면 되므로 실수가 적다

Java에서 스택 크기 주의

Top-Down의 가장 큰 약점은 재귀 깊이 제한이다.

Java 기본 스택 크기는 약 512KB~1MB로, 재귀 깊이 약 1만~3만 정도다. n이 10만 이상이면 StackOverflowError가 날 수 있다.

해결 방법:

// 방법 1: 스레드로 스택 크기 지정
public static void main(String[] args) {
    new Thread(null, () -> {
        // 여기서 Top-Down DP 호출
        solve();
    }, "main", 1 << 26).start();  // 64MB 스택
}

방법 2: Bottom-Up으로 전환
상태 수가 매우 크고 거의 모든 상태를 방문해야 한다면
Bottom-Up이 안전하다.

실전 팁: 시험에서 시간이 부족하면 일단 Top-Down으로 빠르게 구현하고, 스택 문제가 생기면 그때 Bottom-Up으로 바꾸는 전략이 효과적이다.

---

22. DP와 그리디의 차이

둘 다 최적화를 다루지만 다르다.

그리디

지금 당장 가장 좋아 보이는 선택을 한다

DP

가능한 상태를 저장하면서
모든 필요한 선택을 체계적으로 비교한다

예를 들어 어떤 문제가:

• 현재 최선 선택이 미래에도 항상 최선이다 -> 그리디 가능
• 현재 선택이 미래에 미치는 영향이 복잡하다 -> DP 가능성 높음

즉 그리디가 안 보이면 DP를 생각하는 경우가 많다.

---

23. 트리 DP와 비트마스크 DP도 결국 DP다

DP는 배열 한 줄짜리 문제만 뜻하지 않는다.

트리 DP

dp[node]
dp[node][state]

형태로 트리 위에서 진행한다.

비트마스크 DP

dp[mask][last]

처럼 방문 집합과 마지막 위치를 상태로 둔다.

즉 DP의 본질은 자료 구조가 아니라:

상태를 정의하고
그 상태를 이전 상태들로 전이하는 것

이다.

---

24. 자주 하는 실수

1) 상태 정의가 불완전함

현재 답을 결정하는 정보가 상태에 다 들어 있어야 한다.

2) 초기값을 잘못 둠

특히 0, -INF, INF 중 무엇으로 초기화해야 하는지 주의해야 한다.

3) 점화식은 맞는데 계산 순서를 틀림

Bottom-Up에서는 이전 상태가 먼저 계산되어 있어야 한다.

4) 최댓값 문제인데 기본값을 0으로 두면 안 되는 경우

음수 값이 있을 수 있으면 초기값 설계를 더 조심해야 한다.

5) 경우의 수 문제에서 int overflow

경우의 수는 매우 빨리 커진다. long이나 mod 처리가 필요할 수 있다.

6) 완전탐색을 억지로 DP로 착각함

상태 수가 너무 크면 DP도 불가능하다. 즉 상태 수와 전이 수를 같이 계산해야 한다.

---

25. 실전 판단 기준

문제를 보고 아래 조건이 보이면 DP를 먼저 의심하면 된다.

• 작은 답으로 큰 답을 만들 수 있다
• 이전 선택의 결과를 저장하면 다시 쓸 수 있다
• 최댓값, 최솟값, 경우의 수를 묻는다
• 완전탐색은 되지만 중복 계산이 많다
• 배열, 문자열, 트리, 부분집합 상태가 차례로 진행된다

그리고 항상 다음을 적어 보면 된다.

dp[...] = 무엇인가?

이 한 줄이 잡히면 절반은 끝난다.

---

26. 시험장용 최소 암기 버전

DP:
작은 문제 답을 저장해서 큰 문제 만들기

순서:
1. 상태 정의
2. 점화식
3. 초기값
4. 계산 순서
5. 최종 답 위치

자주 나오는 형태:
dp[i]
dp[i][j]
dp[node]
dp[mask]

대표 패턴:
선택 / 비선택
앞에서부터 진행
문자열 두 축 비교
서브트리 합치기

---

27. 최종 요약

DP는 다음 문장으로 정리할 수 있다.

중복되는 작은 문제의 답을 저장해 두고
그 답들로 큰 문제를 만드는 기법

핵심만 다시 압축하면:

• DP의 본질은 상태 정의와 점화식이다
• 초기값과 계산 순서까지 맞아야 한다
• 1차원, 2차원, 트리, 비트마스크 등 형태는 다양하다
• 최댓값, 최솟값, 경우의 수 문제에서 특히 자주 나온다
• 문제를 보면 먼저 dp[...] = 무엇인가를 적어 본다

DP 문제를 풀 때는 항상 이 질문을 하면 된다.

현재 답을 결정하는 최소 정보는 무엇이고,
그 정보를 이전 상태의 답으로 만들 수 있는가?

이 질문의 답이 예라면 DP일 가능성이 높다.