[DP-3] 2차원 DP

Python 코딩테스트 알고리즘 스터디 9주차 — 동적 계획법(DP) 내용을 정리한 글이다.

LCS, 편집 거리, 0/1 배낭 — 두 변수가 동시에 변하는 문제의 점화식 패턴

---

1. 2차원 DP 개념

1차원 DP가 이전 상태 하나 혹은 두 개만 참조했다면, 2차원 DP는 두 개의 변수(인덱스)가 동시에 변하는 문제에서 등장한다. dp[i][j]가 무엇을 의미하는지 먼저 명확히 정의한다. 두 개의 변수가 있다는 것은 보통 두 가지 입력이 동시에 관계를 맺는 상황임을 뜻한다.

대표적인 상황:

• 두 문자열 A, B를 동시에 참조하는 경우 (LCS, 편집 거리)
• 물건 개수와 용량을 동시에 고려하는 경우 (배낭 문제)
• 부분 구간 [i, j]를 고려하는 경우 (구간 DP)

2차원 테이블 초기화

2차원 dp는 테이블로 시각화하면 점화식을 직접 눈으로 확인할 수 있다. 두 문자열 "abc"와 "ac" 사이의 관계라면, 행은 첫 번째 문자열의 인덱스, 열은 두 번째 문자열의 인덱스가 된다.

	""	a	c
""	0	0	0
a	0	?	?
b	0	?	?
c	0	?	?

빈 문자열과의 비교는 항상 0이므로 첫 행과 첫 열을 0으로 초기화한다. 이후 각 칸을 점화식에 따라 채워 나간다.

---

2. LCS (최장 공통 부분 수열)

LCS는 두 문자열에서 순서를 유지하면서 공통으로 등장하는 가장 긴 부분 수열의 길이를 구하는 문제다. 부분 문자열과 다르게 연속일 필요가 없다.

"ABCBDAB"와 "BDCAB"의 LCS는 "BCAB" 또는 "BDAB"로 길이 4다.

dp[i][j]의 의미	문자열 A의 앞 i글자와 문자열 B의 앞 j글자 사이의 LCS 길이
마지막 선택	A[i] == B[j]이면: 두 문자를 LCS에 포함 → dp[i-1][j-1] + 1 A[i] != B[j]이면: 둘 중 하나를 제외한 결과 중 더 큰 것 → max(dp[i-1][j], dp[i][j-1])
점화식	A[i]==B[j]: dp[i][j] = dp[i-1][j-1] + 1 A[i]!=B[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
초기값	dp[0][j] = 0, dp[i][0] = 0

테이블 채우는 과정 — A = "ABCB", B = "BCB"

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

단계별 추적

dp[1][1]: A[1]='A', B[1]='B' → 다름 → max(dp[0][1], dp[1][0]) = max(0,0) = 0
dp[2][1]: A[2]='B', B[1]='B' → 같음 → dp[1][0] + 1 = 0 + 1 = 1
dp[3][1]: A[3]='C', B[1]='B' → 다름 → max(dp[2][1], dp[3][0]) = max(1,0) = 1
dp[3][2]: A[3]='C', B[2]='C' → 같음 → dp[2][1] + 1 = 1 + 1 = 2
dp[4][3]: A[4]='B', B[3]='B' → 같음 → dp[3][2] + 1 = 2 + 1 = 3

def lcs(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 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]) return dp[m][n]

print(lcs("ABCB", "BCB")) print(lcs("ABCBDAB", "BDCAB"))

3 4

LCS 경로 복원

LCS 길이뿐 아니라 실제 수열을 출력해야 할 때는 dp 테이블을 역추적한다. dp[i-1][j]와 dp[i][j-1]을 비교하면서 어느 방향으로 왔는지 역추적하면 된다.

def lcs_with_path(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 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]) result = [] i, j = m, n while i > 0 and j > 0: if a[i - 1] == b[j - 1]: result.append(a[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] > dp[i][j - 1]: i -= 1 else: j -= 1 return dp[m][n], ''.join(reversed(result))

length, path = lcs_with_path("ABCBDAB", "BDCAB") print(length, path)

4 BCAB

---

3. 편집 거리 (Edit Distance)

두 문자열을 같게 만들기 위한 최소 편집 횟수를 구하는 문제다. 가능한 연산은 삽입, 삭제, 교체 세 가지이며 각각 1회로 계산한다.

"horse"를 "ros"로 만들려면 최소 3번의 편집이 필요하다. horse → rorse(h를 r로 교체) → rose(r 삭제) → ros(e 삭제).

dp[i][j]의 의미	문자열 A의 앞 i글자를 문자열 B의 앞 j글자로 변환하는 최소 편집 횟수
마지막 선택	A[i] == B[j]이면: 편집 불필요 → dp[i-1][j-1] A[i] != B[j]이면 세 연산 중 최솟값 + 1   삽입: B[j]를 A에 삽입 → dp[i][j-1] + 1   삭제: A[i]를 삭제 → dp[i-1][j] + 1   교체: A[i]를 B[j]로 교체 → dp[i-1][j-1] + 1
점화식	A[i]==B[j]: dp[i][j] = dp[i-1][j-1] A[i]!=B[j]: dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
초기값	dp[i][0] = i, dp[0][j] = j

테이블 시각화 — A = "horse", B = "ros"

	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

주요 셀 확인

dp[2][2]: A[2]='o', B[2]='o' → 같음 → dp[1][1] = 1
dp[3][1]: A[3]='r', B[1]='r' → 같음 → dp[2][0] = 2
dp[5][3]: 최종 답 = 3

def edit_distance(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) return dp[m][n]

print(edit_distance("horse", "ros")) print(edit_distance("intention", "execution"))

3 5

---

4. 0/1 배낭 문제 (Knapsack)

N개의 물건이 있고 각 물건은 무게 w[i]와 가치 v[i]를 가진다. 무게 합이 용량 W 이하가 되도록 물건을 선택할 때 최대 가치를 구하라. 각 물건은 한 번씩만 사용할 수 있다(0/1).

dp[i][j]의 의미	i번째 물건까지 고려하고 용량이 j일 때 얻을 수 있는 최대 가치
마지막 선택	i번째 물건을 넣지 않는다: dp[i-1][j] i번째 물건을 넣는다 (j >= w[i]일 때): dp[i-1][j - w[i]] + v[i] 더 큰 값 선택
점화식	j < w[i]: dp[i][j] = dp[i-1][j] j >= w[i]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
초기값	dp[0][j] = 0 (물건이 없을 때 가치는 0)

테이블 채우는 과정

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

	0	1	2	3	4	5
물건0	0	0	0	0	0	0
물건1 (w=2, v=3)	0	0	3	3	3	3
물건2 (w=3, v=4)	0	0	3	4	4	7
물건3 (w=4, v=5)	0	0	3	4	5	7

dp[2][5] 계산 과정

물건2(무게=3, 가치=4)를 넣으면 → dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7
넣지 않으면 → dp[1][5] = 3
max(7, 3) = 7

def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if j < weights[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1] ) return dp[n][capacity]

weights = [2, 3, 4] values = [3, 4, 5] capacity = 5 print(knapsack(weights, values, capacity))

7

1차원으로 최적화 — 역순 순회

0/1 배낭 문제는 dp 배열을 1차원으로 줄일 수 있다. 핵심은 용량을 역순으로 순회하는 것이다.

def knapsack_1d(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity]

print(knapsack_1d([2, 3, 4], [3, 4, 5], 5))

7

역순으로 순회하는 이유: dp[j]를 갱신할 때 dp[j - w[i]]가 이미 i번째 물건을 포함한 값으로 갱신되어 있으면 같은 물건이 두 번 선택된다. 역순으로 진행하면 dp[j - w[i]]는 항상 이전 물건까지만 고려된 값이므로 0/1 조건이 유지된다.

---

5. 유형별 정리

유형	dp[i][j]의 의미	점화식 핵심	시간 복잡도
LCS	A[1..i], B[1..j]의 LCS 길이	같으면 +1, 다르면 max(위, 왼쪽)	O(m × n)
편집 거리	A[1..i]를 B[1..j]로 변환하는 최소 횟수	같으면 대각선, 다르면 min(삽입, 삭제, 교체) + 1	O(m × n)
0/1 배낭	i번 물건까지, 용량 j일 때 최대 가치	안 넣기 vs 넣기(이전 행 참조), max 선택	O(n × W)

---

6. Python 자주 쓰는 메서드

2D 리스트 초기화 — 리스트 컴프리헨션

n, m = 4, 5 dp_zero = [[0] * (m + 1) for _ in range(n + 1)] dp_inf = [[float('inf')] * m for _ in range(n)] print(dp_zero[0]) print(dp_inf[0])

[0, 0, 0, 0, 0, 0] [inf, inf, inf, inf, inf]

[[0]*cols]*rows 패턴 금지

[[0]*cols]*rows 패턴은 모든 행이 동일한 리스트 객체를 참조하므로 한 칸을 수정하면 같은 열 전체가 바뀐다. 반드시 리스트 컴프리헨션을 사용해야 한다.

wrong = [[0] * 3] * 3 wrong[0][0] = 99 print(wrong) correct = [[0] * 3 for _ in range(3)] correct[0][0] = 99 print(correct)

[[99, 0, 0], [99, 0, 0], [99, 0, 0]] [[99, 0, 0], [0, 0, 0], [0, 0, 0]]

Bottom-Up 이중 순회 — 표준 패턴

a = "ABCB" b = "BCB" m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 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]) print(dp[m][n])

3

for i in range(1, m+1): for j in range(1, n+1): 구조는 2차원 DP Bottom-Up의 표준 패턴이다. 행과 열을 1부터 시작하면 경계 처리를 별도로 하지 않아도 된다.

dp[i][j] = max(...) — 전이 패턴

weights = [2, 3, 4] values = [3, 4, 5] capacity = 5 n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if j < weights[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1] ) print(dp[n][capacity])

7

여러 방향에서 전이가 가능할 때 max() 또는 min()으로 최적 전이를 선택하는 패턴이 2차원 DP의 핵심이다.

zip() — 두 시퀀스 비교

a = "ABCB" b = "BCB" for ca, cb in zip(a, b): print(ca, cb, ca == cb)

A B False B C False C B False B B True

LCS처럼 두 문자열을 비교할 때 zip()으로 같은 위치의 문자를 쌍으로 묶어 처리할 수 있다. 단, LCS는 오프셋이 달라지므로 실제 구현에서는 인덱스를 직접 사용하는 경우가 많다.

---

7. 연습 문제

초급

번호	문제	난이도	핵심 접근
43105	정수 삼각형	Lv.3	꼭대기부터 최댓값 누적, 2차원 DP 타뷸레이션 적용
42898	등굣길	Lv.3	격자 이동 DP, dp[i][j] = dp[i-1][j] + dp[i][j-1]

중급

번호	문제	난이도	핵심 접근
12904	가장 긴 팰린드롬	Lv.3	is_palindrome[i][j] 테이블 구성, 구간 DP로 팰린드롬 판별
42897	도둑질	Lv.4	원형 집 도둑, 첫 집 포함/미포함 두 경우를 분리해 비교