Ch.10 다이나믹 프로그래밍
2D DP — Unique Paths, 0/1 Knapsack
격자 위에서 길을 찾아라
m×n 격자의 좌상단에서 우하단까지 오른쪽/아래로만 이동할 때 경로의 수는? 이 문제로 2D DP의 세계에 입문합니다.
1차원 배열로는 부족하다. 행과 열, 두 차원을 어떻게 다루지?
dp[i][j] — 2차원 테이블의 각 칸을 채우면 답이 보입니다.
핵심 개념
2D DP
두 개의 인덱스(i, j)로 상태를 표현하는 DP
0/1 Knapsack
각 물건을 넣거나 안 넣거나 선택하는 최적화 문제
핵심 내용
Unique Paths (LeetCode #62) m×n 격자에서 경로의 수를 구합니다
점화식: dp[i][j] = dp[i-1][j] + dp[i][j-1] (i, j)에 도달하려면: • 위에서 내려오거나 (i-1, j) • 왼쪽에서 오거나 (i, j-1) 기저 사례: 첫 행과 첫 열은 모두 1
2D dp 테이블을 채우고 공간 최적화까지 해봅시다
def uniquePaths(m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# 3x3 격자:
# [[1, 1, 1],
# [1, 2, 3],
# [1, 3, 6]] → 답: 6# 공간 최적화: 2D → 1D
def uniquePaths(m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # 위 + 왼쪽
return dp[n-1]
# 현재 행은 이전 행에만 의존 → 1D 배열로 충분!시간 O(m×n), 공간 O(n). 2D를 1D로 압축하는 롤링 배열 기법!
DP의 클래식 문제 배낭에 물건을 담아봅시다
0/1 배낭 문제: 무게 제한 W인 배낭에 n개의 물건(무게 w[i], 가치 v[i])을 넣어서 최대 가치를 구하라 각 물건은 넣거나(1) 안 넣거나(0) — 0/1
점화식: dp[i][w] = 처음 i개 물건, 무게 제한 w일 때 최대 가치 w[i] > w (못 넣음): dp[i][w] = dp[i-1][w] w[i] <= w (선택): dp[i][w] = max( dp[i-1][w], # 안 넣는다 dp[i-1][w-w[i]] + v[i] # 넣는다 )
배낭 문제를 코드로 구현합니다
def knapsack(W: int, weights: list, values: list) -> int:
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
dp[i][w] = dp[i-1][w] # 안 넣는다
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][W]
# 예: W=7, weights=[1,3,4,5], values=[1,4,5,7]
# 답: 9 (무게 3+4=7, 가치 4+5=9)# 공간 최적화: 1D (역순 순회!)
def knapsack(W: int, weights: list, values: list) -> int:
dp = [0] * (W + 1)
for i in range(len(weights)):
for w in range(W, weights[i] - 1, -1): # 역순!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]1D 최적화 시 역순 순회가 핵심! 순방향이면 같은 물건을 여러 번 쓰게 됩니다
2D DP 문제의 공통 패턴을 정리합니다
2D DP 공통 패턴: • 격자 경로: dp[i][j] = 위 + 왼쪽 • 배낭 문제: dp[i][w] = max(넣기, 안 넣기) • 문자열 비교: dp[i][j] = 글자 비교 전이 공간 최적화: • 현재 행이 이전 행에만 의존 → 1D 배열 • 0/1 선택 → 역순 순회 필수
uniquePaths(3, 3)의 결과는?
0/1 Knapsack의 1D 최적화에서 무게를 역순으로 순회해야 한다
2D DP 정복!
핵심 용어
2D DP
두 인덱스 (i, j)로 상태를 표현하는 DP
0/1 Knapsack
각 물건을 넣거나/안 넣거나 선택하는 최적화
정리 노트
2D DP — Unique Paths, 0/1 Knapsack
Unique Paths
- 점화식
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
- 공간 최적화
- 2D → 1D 롤링 배열
0/1 Knapsack
- 점화식
- dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i)
- 1D 최적화
- 역순 순회 필수 (중복 선택 방지)
배낭 문제는 면접에서 직접 나오기보다, 다른 문제의 '모델링 틀'로 자주 쓰입니다!
시각 자료
핵심 정리
- 1Unique Paths: dp[i][j] = 위 + 왼쪽
- 20/1 Knapsack: 넣거나/안 넣거나 선택
- 32D → 1D 공간 최적화 (롤링 배열, 역순)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작