배낭 문제 Knapsack 해결법: 그리디와 DP의 완벽 선택 가이드

제한된 자원 속에서 최대의 효율을 뽑아내야 하는 상황은 경영학, 물류, 그리고 컴퓨터 공학에서 가장 빈번하게 마주하는 최적화 문제입니다. 그중에서도 배낭 문제(Knapsack Problem)는 조건에 따라 해결 전략이 완전히 달라지는 독특한 특성을 가지고 있습니다. 물건을 쪼갤 수 있느냐 없느냐에 따라 그리디(Greedy)와 동적 계획법(Dynamic Programming) 중 무엇을 선택해야 할지 결정됩니다. 본 포스팅에서는 배낭 문제의 두 가지 유형과 각 상황에 맞는 최적의 해법을 2,500자 이상의 상세한 설명으로 정리해 보겠습니다.

1. 배낭 문제의 두 가지 유형 정의

배낭 문제는 담을 수 있는 최대 무게가 정해진 배낭과, 각각의 무게와 가치를 가진 물건들이 주어졌을 때 배낭에 담긴 물건들의 가치 합이 최대가 되도록 구성하는 문제입니다. 이 문제는 물건의 성질에 따라 두 가지로 나뉩니다.

• 분수 배낭 문제 (Fractional Knapsack): 물건을 쪼개서 담을 수 있는 경우입니다. (예: 설탕, 금가루)
• 0-1 배낭 문제 (0-1 Knapsack): 물건을 통째로 담거나 아예 담지 않아야 하는 경우입니다. (예: 노트북, 카메라)

2. 분수 배낭 문제의 해법: 탐욕 알고리즘(Greedy)

물건을 쪼갤 수 있다면 문제는 매우 단순해집니다. 무게당 가치가 가장 높은 물건부터 순서대로 배낭에 채우면 되기 때문입니다. 이를 그리디(Greedy) 방식이라고 합니다. 배낭이 가득 차기 직전에는 남은 용량만큼 물건을 쪼개서 넣으면 항상 전역 최적해(Global Optimum)를 얻을 수 있습니다.

2-1. 그리디 전략의 정당성

가성비(가치/무게)가 높은 물건을 먼저 담는 행위는 단위 무게당 얻을 수 있는 이득을 극대화하는 행위이므로, 물건을 쪼갤 수 있는 환경에서는 이보다 더 좋은 해가 존재할 수 없습니다. 시간 복잡도는 물건을 정렬하는 데 걸리는 $O(N \log N)$이 지배적입니다.

3. 0-1 배낭 문제의 해법: 동적 계획법(DP)

물건을 쪼갤 수 없다면 그리디 방식은 무너집니다. 가성비는 좋지만 무게가 너무 커서 배낭의 남은 공간을 애매하게 만드는 물건보다는, 가성비는 조금 떨어져도 무게 조절이 쉬운 물건들의 조합이 더 높은 가치를 낼 수 있기 때문입니다. 이때 우리는 모든 경우의 수를 체계적으로 검토하는 동적 계획법(Dynamic Programming)을 사용합니다.

3-1. DP 점화식과 상태 정의

우리는 2차원 배열 dp[i][w]를 생성합니다. 이는 "첫 번째부터 $i$번째 물건까지 고려했을 때, 배낭 용량이 $w$인 상황에서의 최대 가치"를 의미합니다. 점화식은 다음과 같습니다.

$dp[i][w] = \max(dp[i-1][w], dp[i-1][w - w_i] + v_i)$

현재 물건을 넣지 않는 경우와, 넣었을 때의 가치를 비교하여 더 큰 값을 취하는 논리입니다. 이를 통해 모든 부분 문제의 최적해를 누적하여 전체 최적해를 찾아냅니다.

4. 실무적 선택 기준 및 최적화 팁

0-1 배낭 문제는 시간 복잡도가 $O(N \times K)$ (K는 배낭 무게)로, $K$가 매우 클 경우 계산량이 많아질 수 있습니다. 실무에서는 이를 1차원 배열로 압축하여 공간 복잡도를 최적화하거나, 물건의 무게가 너무 클 경우 근사 알고리즘(Approximation Algorithm)을 사용하기도 합니다. 중요한 것은 현재 마주한 문제가 '연속적인 자원'을 다루는지, '독립적인 개체'를 다루는지 파악하여 올바른 알고리즘 도구를 꺼내는 것입니다.

[배낭 문제 핵심 요약]
1. 분수형: 물건을 쪼갤 수 있으며, 무게당 가치 기준의 그리디로 $O(N \log N)$ 만에 해결합니다.
2. 0-1형: 물건을 쪼갤 수 없으며, 모든 조합을 고려하는 DP를 사용하여 $O(NK)$에 해결합니다.
3. 핵심: 문제의 제약 조건을 분석하여 탐욕적 선택이 유효한지 먼저 판단하는 것이 설계의 핵심입니다.