배낭 문제가 DP의 대표 예제가 된 이유는, 점화식을 외우기 쉬워서가 아니라 상태를 어떻게 정의해야 하는지 가장 또렷하게 보여주기 때문입니다. 0/1 Knapsack을 제대로 이해하면 DP를 문제 풀이 관점에서 훨씬 덜 막히게 볼 수 있습니다.
이번 글에서는 0/1 Knapsack을 기준으로 왜 완전탐색이 느려지는지, 왜 그리디가 항상 통하지 않는지, 그리고 dp[i][w]라는 상태가 왜 자연스럽게 등장하는지 단계적으로 정리하겠습니다. DP 전체 감각이 먼저 필요하다면 동적 계획법(DP) 쉽게 이해하기 글을 먼저 보고 와도 좋습니다.
배낭 문제는 정확히 어떤 문제일까
0/1 Knapsack에서는 각 물건마다 무게와 가치가 있습니다. 배낭의 최대 허용 무게가 정해져 있을 때, 물건을 일부 골라 총무게는 넘기지 않으면서 총가치를 최대화해야 합니다. 여기서 0/1이라는 말은 각 물건을 한 번만 담을 수 있다는 뜻입니다. 배낭 문제의 고전적 정의는 Knapsack problem 개요에서도 같은 구조로 설명됩니다.
예를 들어 물건이 4개 있고, 배낭 용량이 7이라고 해보겠습니다. 각 물건을 넣을지 말지 결정해야 하므로 직관적으로는 모든 조합을 다 살펴보고 싶어집니다. 실제로 가장 먼저 떠오르는 방법은 완전탐색입니다.
왜 완전탐색으로 풀면 금방 느려질까
물건이 n개면 각 물건마다 담는다 / 안 담는다 두 선택이 있습니다. 그래서 가능한 조합 수는 대략 2^n으로 늘어납니다. 물건 수가 조금만 커져도 경우의 수가 급격히 폭발합니다.
여기서 중요한 것은, 완전탐색이 항상 틀린 방법이라는 뜻이 아니라는 점입니다. 작은 입력에서는 충분히 맞는 접근일 수 있습니다. 하지만 코딩테스트나 알고리즘 문제에서는 물건 수와 용량이 커지면서, 같은 계산을 계속 반복하게 되는 구조가 나타납니다.
왜 그리디로는 항상 안전하지 않을까
배낭 문제를 처음 보면 가치가 큰 물건부터 담거나, 무게 대비 가치가 큰 물건부터 담고 싶어집니다. 하지만 0/1 Knapsack에서는 이 직감이 항상 안전하지 않습니다. 지금 좋아 보이는 선택이 남은 용량을 애매하게 만들어서, 전체 최적해를 막을 수 있기 때문입니다.
예를 들어 용량이 10이고, 물건이 (무게 6, 가치 30), (무게 5, 가치 24), (무게 4, 가치 20)라고 해보겠습니다. 가치가 가장 큰 30짜리를 먼저 담으면 남은 용량은 4가 되어 총가치 50이 됩니다. 하지만 5와 4를 담으면 총가치 44라서 이 예시는 첫 선택이 더 좋습니다. 그런데 입력이 조금만 바뀌어도 상황은 쉽게 뒤집힙니다.
즉 0/1 Knapsack은 당장 가장 좋아 보이는 선택이 항상 전체 최적을 보장하지 않는다는 점에서, 그리디보다 DP 쪽 감각이 더 중요합니다. 그리디 판단 기준은 그리디 알고리즘이 어려운 이유 글과 함께 보면 더 분명해집니다.
DP에서 정말 중요한 것은 점화식보다 상태 정의다
배낭 문제를 외워서 풀려는 사람은 보통 점화식부터 봅니다. 하지만 실제로 더 중요한 것은 무엇을 상태로 둘 것인가입니다. 상태 정의가 명확해지면 점화식은 거의 자연스럽게 따라옵니다.
가장 대표적인 정의는 dp[i][w]입니다. 이것은 앞에서부터 i개 물건만 고려했을 때, 배낭 용량이 w일 때 얻을 수 있는 최대 가치를 뜻합니다.
이 정의가 좋은 이유는 현재 상태를 설명하는 데 필요한 정보가 정확히 담겨 있기 때문입니다. 지금 몇 번째 물건까지 봤는지, 남은 판단 기준인 용량이 얼마인지 알면 다음 선택을 구성할 수 있습니다.
점화식은 왜 담는다 / 안 담는다 두 갈래로 나뉠까
i번째 물건의 무게를 weight[i], 가치를 value[i]라고 해보겠습니다. 현재 용량이 w일 때 가능한 선택은 두 가지뿐입니다.
- i번째 물건을 담지 않는다
- i번째 물건을 담는다. 단, 무게가 w 이하여야 한다
따라서 점화식은 다음처럼 나옵니다.
if weight[i] > w:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - weight[i]] + value[i]
)여기서 핵심은 수식이 아니라 의미입니다. 담지 않으면 이전 상태를 그대로 가져오고, 담는다면 남은 용량 = w - weight[i] 상태에서 얻을 수 있는 최댓값에 현재 물건 가치를 더합니다. 즉 지금 선택 하나가 이전 상태와 정확히 이어집니다.
작은 예시로 상태표를 읽어보자
예를 들어 물건이 (6,13), (4,8), (3,6), (5,12)이고 배낭 용량이 7이라면, dp[i][w] 표는 각 물건을 하나씩 추가해 가며 채워집니다. 첫 번째 물건만 볼 때는 용량 6 이상에서 가치 13을 만들 수 있습니다. 두 번째 물건까지 보면 용량 4에서 가치 8, 용량 7에서 13이 유지됩니다.
세 번째 물건까지 보면 용량 7에서 (4,8)과 (3,6)을 함께 담아 가치 14를 만들 수 있습니다. 이 순간이 중요합니다. DP는 “지금 당장 제일 좋아 보이는 물건”을 고르는 대신, 이전까지의 최선 결과를 재사용하면서 더 좋은 조합이 생기는지를 누적해서 확인합니다.
items = [(6, 13), (4, 8), (3, 6), (5, 12)]
capacity = 7
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(capacity + 1):
if weight > w:
dp[i][w] = dp[i - 1][w]
else:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
print(dp[n][capacity]) # 14왜 1차원 배열로도 줄일 수 있을까
2차원 DP를 보면 현재 행은 바로 이전 행만 참고합니다. 그래서 메모리를 줄이고 싶다면 dp[w] 하나만 두고 갱신할 수 있습니다. 다만 여기서 가장 자주 틀리는 부분이 순회 방향입니다.
0/1 Knapsack에서는 같은 물건을 한 번만 써야 하므로, 용량을 큰 값에서 작은 값으로 역순 순회해야 합니다. 그래야 같은 물건이 같은 단계에서 두 번 반영되지 않습니다.
items = [(6, 13), (4, 8), (3, 6), (5, 12)]
capacity = 7
dp = [0] * (capacity + 1)
for weight, value in items:
for w in range(capacity, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
print(dp[capacity]) # 14만약 앞에서부터 순회하면, 방금 갱신한 값을 같은 물건이 다시 읽게 됩니다. 그러면 0/1 문제가 아니라 같은 물건을 여러 번 쓸 수 있는 unbounded knapsack처럼 동작할 수 있습니다.
배낭 문제가 DP 입문자에게 특히 좋은 이유
추가로 많이 헷갈리는 지점이 하나 더 있습니다. 배낭 문제를 이해했다고 해서 완전 배낭까지 같은 방식으로 생각하면 쉽게 꼬입니다. 0/1 배낭은 한 물건을 한 번만 쓸 수 있지만, 완전 배낭은 같은 물건을 여러 번 쓸 수 있기 때문에 1차원 최적화에서 순회 방향도 달라집니다.
즉 배낭 문제는 DP의 대표 예제이면서도, 같은 듯 다른 변형 문제를 통해 상태 정의와 순회 방향이 왜 중요한지까지 한 번에 보여주는 좋은 훈련장입니다.
- 상태 정의의 필요성을 강하게 보여준다
- 담는다 / 안 담는다라는 이진 선택 구조가 분명하다
- 완전탐색과 DP 차이를 체감하기 좋다
- 2차원에서 1차원 최적화로 확장하기 좋다
- 그리디가 항상 통하지 않는 이유도 같이 설명할 수 있다
즉 배낭 문제는 단순한 대표 문제라서 유명한 것이 아니라, DP 사고 흐름을 한 문제 안에서 거의 모두 보여줄 수 있기 때문에 대표 예제가 되었습니다.
문제를 읽을 때 스스로 던질 질문
- 선택할 때마다 상태가 무엇으로 요약되는가
- 현재 선택 이후에 필요한 정보는 몇 번째까지 봤는지와 남은 용량인가
- 같은 하위 문제가 여러 번 반복되는가
- 현재 최적이 이전 최적 결과와 연결되는가
이 질문에 자연스럽게 답이 잡히면, 배낭 문제뿐 아니라 많은 DP 문제에서 상태 정의를 더 빠르게 떠올릴 수 있습니다.
마무리
배낭 문제가 DP의 대표 예제가 된 이유는, 점화식을 예쁘게 만들기 쉬워서가 아닙니다. 물건을 담을지 말지 선택하는 과정에서 상태 정의, 이전 결과 재사용, 1차원 최적화, 순회 방향까지 한 번에 훈련할 수 있기 때문입니다.
앞으로 배낭 문제를 볼 때는 공식을 먼저 외우기보다, dp[i][w]가 정확히 무엇을 뜻하는지부터 스스로 설명해 보세요. 그 순간부터 DP가 훨씬 덜 추상적으로 느껴질 것입니다.
