1차원 DP는 2차원 DP 테이블을 무작정 줄이는 기술이 아닙니다. 현재 상태를 계산할 때 어떤 이전 값이 필요한지 확인한 뒤, 덮어써도 안전할 때만 쓸 수 있는 메모리 최적화입니다.
가장 중요한 기준은 현재 칸을 계산할 때 아직 써야 하는 값을 덮어쓰지 않는가입니다. 이 기준을 놓치면 코드는 짧아지지만 답은 조용히 틀립니다.
2차원 DP를 먼저 생각해야 하는 이유
처음부터 1차원 DP로 시작하면 전이 관계가 잘 보이지 않습니다. 예를 들어 물건 i까지 고려했을 때 무게 w에서의 최댓값은 보통 dp[i][w]처럼 생각하는 편이 자연스럽습니다.
dp[i][w] =
i번째 물건까지 고려했고
가방 용량이 w일 때 만들 수 있는 최대 가치이렇게 2차원으로 정의하면 행은 선택한 물건 범위, 열은 용량을 의미합니다. 그다음 현재 행이 이전 행만 참조하는지 확인하면 1차원으로 줄일 수 있는지 판단할 수 있습니다.
줄여도 되는 핵심 조건
2차원 DP에서 dp[i][w]가 dp[i-1][…]만 참조한다면, i-1행 전체를 따로 보관하지 않고 같은 배열을 갱신할 수 있습니다. 다만 같은 배열을 쓰는 순간 dp[w]는 이전 행 값일 수도 있고, 이미 현재 행으로 갱신된 값일 수도 있습니다.
- 이전 행 값만 필요하면 1차원 배열 후보가 된다
- 현재 행에서 갱신된 값을 다시 쓰면 문제가 되는지 확인한다
- 문제가 된다면 순회 방향을 바꿔 덮어쓰기를 피한다
- 전이식보다 순회 순서가 더 중요해지는 순간이 있다
0/1 knapsack은 왜 역순으로 도는가
0/1 knapsack에서는 각 물건을 한 번만 쓸 수 있습니다. 그런데 용량을 작은 값에서 큰 값으로 정순 순회하면, 방금 넣은 물건을 같은 i단계에서 다시 쓰는 효과가 생길 수 있습니다.
# 0/1 knapsack: 같은 물건을 한 번만 써야 하므로 역순
for weight, value in items:
for w in range(capacity, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)역순으로 돌면 dp[w – weight]는 아직 현재 물건으로 갱신되기 전 값입니다. 그래서 같은 물건을 한 번만 쓰는 조건이 유지됩니다.
정순으로 돌면 어떤 버그가 생길까
물건 하나의 무게가 3, 가치가 5라고 해 보겠습니다. 정순으로 w=3을 갱신한 뒤 w=6을 계산하면 dp[3]이 이미 5가 되어 있습니다. 그러면 같은 물건을 두 번 넣은 것처럼 dp[6]=10이 될 수 있습니다.
capacity = 6
item = (weight=3, value=5)
정순 갱신:
dp[3] = 5
dp[6] = dp[3] + 5 = 10 # 같은 물건을 두 번 쓴 효과unbounded knapsack은 왜 정순이 자연스러운가
unbounded knapsack은 같은 물건을 여러 번 쓸 수 있습니다. 이 경우에는 현재 단계에서 갱신된 dp[w – weight]를 다시 사용하는 것이 오히려 의도와 맞습니다.
# unbounded knapsack: 같은 물건을 여러 번 쓸 수 있으므로 정순
for weight, value in items:
for w in range(weight, capacity + 1):
dp[w] = max(dp[w], dp[w - weight] + value)같은 전이식처럼 보여도 문제의 선택 조건이 달라지면 순회 방향이 달라집니다. 그래서 1차원 DP에서는 코드를 외우기보다 덮어쓰기 의미를 읽어야 합니다.
순회 방향을 고르는 질문
- 현재 선택을 같은 단계에서 다시 써도 되는가
- dp[w – x]가 이전 행 값이어야 하는가
- 현재 행에서 갱신된 값이어도 되는가
- 작은 인덱스에서 큰 인덱스로 가면 중복 사용이 생기는가
- 큰 인덱스에서 작은 인덱스로 가면 필요한 값이 사라지는가
1차원 DP로 줄이면 안 되는 경우
모든 2차원 DP가 1차원으로 쉽게 줄어드는 것은 아닙니다. 현재 값이 이전 행뿐 아니라 같은 행의 여러 방향, 대각선, 혹은 복잡한 범위를 동시에 참조한다면 단순한 1차원 배열 하나로는 상태를 보존하기 어렵습니다.
- 경로 복원이 필요해 전체 선택 기록을 남겨야 하는 경우
- 현재 행의 왼쪽과 이전 행을 섞어 참조하는 경우
- 상태 차원이 의미적으로 독립적이라 압축하면 설명이 무너지는 경우
- 메모리는 줄지만 버그 가능성이 크게 올라가는 경우
실전 체크리스트
- 먼저 2차원 dp 정의를 문장으로 쓴다
- 전이식이 어떤 행과 열을 참조하는지 표시한다
- 같은 배열로 갱신했을 때 덮어쓰기 위험을 찾는다
- 순회 방향을 바꾸면 위험이 사라지는지 확인한다
- 작은 예제로 중복 사용 여부를 직접 추적한다
DP 테이블 최적화 정리
1차원 DP의 핵심은 배열 크기를 줄이는 데 있지 않습니다. 현재 상태를 계산할 때 필요한 이전 값이 무엇인지, 그 값이 갱신 과정에서 덮어써지는지 이해하는 데 있습니다.
0/1 knapsack은 역순, unbounded knapsack은 정순이라는 암기는 출발점일 뿐입니다. 진짜 기준은 같은 선택을 다시 써도 되는지입니다. 관련 배경은 CP-Algorithms knapsack 정리와 knapsack이 DP의 대표 문제인 이유를 함께 보면 좋습니다.
