0-1 배낭 문제 Knapsack 알고리즘 DP 응용 해설

제한된 자원 속에서 최대의 효율을 뽑아내야 하는 상황은 경영학, 물류, 그리고 컴퓨터 공학에서 가장 빈번하게 마주하는 최적화 문제입니다. 그중에서도 0-1 배낭 문제(0-1 Knapsack Problem)는 동적 계획법(Dynamic Programming)의 정수라고 불릴 만큼 정교한 논리 구조를 가지고 있습니다. 단순히 가성비가 좋은 물건부터 담는 '그리디(Greedy)' 방식으로는 해결할 수 없는 이 문제의 본질을 파헤치고, 전역 최적해를 찾아가는 DP의 마법 같은 과정을 상세히 정리해 보겠습니다.

1. 배낭 문제의 정의와 그리디 알고리즘의 한계

배낭 문제는 담을 수 있는 최대 무게가 정해진 배낭과, 각각의 무게와 가치를 가진 물건들이 주어졌을 때 배낭에 담긴 물건들의 가치 합이 최대가 되도록 구성하는 문제입니다. 여기서 '0-1'이라는 수식어가 붙는 이유는 물건을 쪼개서 담을 수 없고, '담거나(1) 담지 않거나(0)'의 선택지뿐이기 때문입니다. 만약 물건을 설탕이나 밀가루처럼 쪼갤 수 있다면 가성비(가치/무게) 순으로 담는 그리디 알고리즘이 통하지만, 쪼갤 수 없는 0-1 배낭 문제에서는 그리디 방식이 최적해를 보장하지 못합니다. 예를 들어 가성비는 좋지만 무게가 너무 커서 다른 고가치 물건들을 담지 못하게 되는 상황이 발생하기 때문입니다.

1-1. 동적 계획법으로의 접근: 상태 정의

DP로 이 문제를 해결하기 위해서는 문제를 작은 단위로 쪼개야 합니다. 우리는 두 가지 변수를 고려해야 합니다. 첫 번째는 '고려할 물건의 인덱스'이고, 두 번째는 '현재 배낭의 임시 용량'입니다. 이를 2차원 배열 dp[i][w]로 정의합니다. 여기서 i는 첫 번째부터 i번째 물건까지 고려했다는 의미이고, w는 현재 배낭의 무게 한도를 뜻합니다. 이 배열의 최종 목적지인 dp[N][K](N은 물건 개수, K는 배낭 최대 무게)에 우리가 원하는 최대 가치가 저장됩니다.

2. 점화식 도출과 배낭 채우기 프로세스

이제 가장 중요한 논리인 점화식을 세울 차례입니다. i번째 물건을 검사할 때, 우리는 두 가지 경우의 수를 따집니다. 첫째는 물건을 담지 않는 경우입니다. 이 경우 가치는 이전 단계의 값인 dp[i-1][w]와 동일합니다. 둘째는 물건을 담는 경우입니다. 단, 물건의 무게 $w_i$가 현재 배낭 용량 $w$보다 작거나 같아야 합니다. 이때의 가치는 i번째 물건의 가치 $v_i$에, 이 물건을 넣기 위해 비워둔 공간의 이전 최적 가치인 dp[i-1][w - w_i]를 더한 값이 됩니다.

2-1. 핵심 점화식의 수학적 표현

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

이 식은 "현재 물건을 안 넣었을 때의 최선"과 "현재 물건을 넣었을 때의 최선" 중 더 큰 값을 선택한다는 뜻입니다. 이 과정을 1번 물건부터 $N$번 물건까지, 무게 1부터 $K$까지 2중 루프를 돌며 테이블을 채워나가면 전역 최적해에 도달하게 됩니다.

3. 공간 복잡도 최적화: 1차원 배열로의 전환

2차원 배열을 사용하면 $O(N \times K)$의 공간이 필요합니다. 하지만 자세히 살펴보면 i번째 행을 계산할 때 오직 i-1번째 행의 정보만 필요하다는 것을 알 수 있습니다. 이를 이용해 1차원 배열만으로도 문제를 풀 수 있습니다. 이때 주의할 점은 무게를 뒤에서부터(역순으로) 갱신해야 한다는 것입니다. 앞에서부터 갱신하면 이번 단계에서 넣은 물건이 같은 단계에서 또 반영되는 '중복 선택' 오류가 발생하기 때문입니다. 이러한 최적화는 메모리 사용량을 획기적으로 줄여 실무적인 환경에서 대규모 데이터를 처리할 때 필수적인 기법입니다.

# 1차원 배열을 이용한 최적화된 0-1 배낭 문제 구현 (Python)
def knapsack(n, k, items):
    dp = [0] * (k + 1)
    for w_i, v_i in items:
        # 역순 탐색으로 중복 선택 방지
        for j in range(k, w_i - 1, -1):
            dp[j] = max(dp[j], dp[j - w_i] + v_i)
    return dp[k]

4. 배낭 문제의 확장과 실무적 응용

0-1 배낭 문제는 단순히 알고리즘 퍼즐에 그치지 않습니다. 한정된 예산 내에서의 마케팅 채널 포트폴리오 구성, 서버 용량에 따른 작업 스케줄링, 투자 자산의 비중 결정 등 자원 배분 최적화가 필요한 모든 영역에 기본 모델로 활용됩니다. 또한 이 기초 모델을 이해하면 물건을 여러 번 담을 수 있는 'Unbounded Knapsack'이나 물건을 쪼갤 수 있는 'Fractional Knapsack' 등 더 복잡한 변형 문제도 능숙하게 다룰 수 있는 토대를 마련하게 됩니다.

[0-1 배낭 문제 핵심 요약]
1. 본질: 물건을 쪼갤 수 없는 환경에서 그리디의 한계를 극복하고 DP로 최적해를 찾습니다.
2. 논리: 현재 물건을 포함할지 말지를 이전 단계의 최적해와 비교하여 결정합니다.
3. 최적화: 1차원 배열과 역순 탐색을 통해 공간 복잡도를 $O(K)$로 최적화할 수 있습니다.