동적 프로그래밍 (DP) — 2차원

관련 문제

문제	난이도	핵심
정수 삼각형	Lv.3	2차원 DP 기초
longest common subsequence	Lv.4	LCS 점화식
등굣길	Lv.3	격자 경로 DP

---

1. 개념

2차원 DP는 상태가 두 개의 변수로 결정될 때 사용한다.

1차원 DP가 dp[i]로 상태를 표현했다면, 2차원 DP는 dp[i][j]로 표현한다.

dp[i][j] = 행 i, 열 j에서의 최적값
         = 문자열 i번째, j번째까지 고려했을 때의 최적값
         = i번째 물건까지, 무게 j까지 담을 수 있을 때의 최적값

상태가 2개라는 것만 다를 뿐, 점화식을 세우는 방식은 1차원 DP와 동일하다.

---

2. 동작 과정

격자 경로 — (0,0)에서 (3,3)까지 가는 경우의 수

좌측 또는 위쪽에서만 올 수 있다고 할 때, 점화식은 다음과 같다.

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

	0	1	2	3
0	1	1	1	1
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20

왼쪽과 위쪽 값을 더하면서 채워나가면 된다.

---

3. 대표 유형 2가지

LCS (최장 공통 부분 수열)

두 문자열에서 공통으로 등장하는 가장 긴 부분 수열의 길이를 구한다.

s1 = "ABCDE"
s2 = "ACE"
LCS = "ACE" → 길이 3

점화식

s1[i] == s2[j] 이면 → dp[i][j] = dp[i-1][j-1] + 1
s1[i] != s2[j] 이면 → dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

배낭 문제 (Knapsack)

무게 제한이 있을 때 가치의 합을 최대화한다.

dp[i][j] = i번째 물건까지 고려하고, 무게 j까지 담을 수 있을 때 최대 가치

점화식

물건 i를 담지 않는 경우 → dp[i][j] = dp[i-1][j]
물건 i를 담는 경우      → dp[i][j] = dp[i-1][j - weight[i]] + value[i]
둘 중 큰 값을 선택

---

4. 핵심 포인트 2가지

dp[i][j]의 정의가 전부다

2차원 DP는 상태가 두 개라 정의를 잘못 잡으면 점화식 자체가 틀린다. 코드 짜기 전에 반드시 먼저 정의부터 써라.

// 격자 경로
dp[i][j] = (0,0)에서 (i,j)까지 오는 경우의 수

// LCS
dp[i][j] = s1의 i번째, s2의 j번째까지 고려했을 때 LCS 길이

// 배낭
dp[i][j] = i번째 물건까지 고려하고 무게 j까지 담을 수 있을 때 최대 가치

초기화 범위가 넓어진다

1차원은 dp[0], dp[1]만 초기화하면 됐지만, 2차원은 첫 번째 행과 열 전체를 초기화해야 하는 경우가 많다.

// 격자 경로 초기화
for (int i = 0; i < n; i++) dp[i][0] = 1;  // 첫 번째 열
for (int j = 0; j < m; j++) dp[0][j] = 1;  // 첫 번째 행

---

5. 코드

격자 경로

int gridPath(int n, int m) {
    int[][] dp = new int[n][m];

    for (int i = 0; i < n; i++) dp[i][0] = 1;
    for (int j = 0; j < m; j++) dp[0][j] = 1;

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

LCS

int lcs(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

배낭 문제 (0/1 Knapsack)

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

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            dp[i][j] = dp[i - 1][j];  // 담지 않는 경우
            if (j >= weight[i - 1]) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

---

6. 시간복잡도

유형	시간복잡도	공간복잡도
격자 경로	O(N × M)	O(N × M)
LCS	O(N × M)	O(N × M)
배낭 문제	O(N × W)	O(N × W)

N, M은 문자열 길이 또는 행/열 크기, W는 무게 제한이다.

---

7. 주의사항

• dp[i][j] 정의를 먼저 써라. 2차원은 상태가 두 개라 정의가 흔들리면 점화식도 흔들린다.
• 배열 크기를 +1로 잡아라. LCS나 배낭처럼 인덱스 0을 초기값으로 쓰는 경우가 많아서 new int[n + 1][m + 1]로 선언하는 게 안전하다.
• 초기화를 빠뜨리지 마라. 첫 번째 행, 첫 번째 열을 초기화하지 않으면 전체 계산이 틀린다.
• 공간 최적화가 가능한 경우가 있다. 배낭 문제는 이전 행만 참조하기 때문에 1차원 배열로 줄일 수 있다. 단, 순회 방향에 주의해야 한다.