0/1 배낭 문제와 동적계획법 정리, DP 표를 직접 채워 보고 탐욕법이 실패하는 이유까지

정해진 무게만 담을 수 있는 가방에 가치가 가장 크도록 물건을 고르는 문제는 예산 배분, 서버 자원 할당, 광고 슬롯 선택처럼 모양만 바뀌어 계속 등장합니다. 0/1 배낭 문제는 동적계획법(DP)을 설명하는 가장 대표적인 예제라 알고리즘 설계 기법 문제에 자주 쓰입니다.

0/1 배낭 문제란 무엇인가

여행 가방에 최대 7kg까지만 넣을 수 있다고 해 봅시다. 앞에 놓인 물건은 저마다 무게와 가치(쓸모)가 다릅니다. 이때 무게 한도를 넘지 않으면서 가치의 합이 가장 커지도록 어떤 물건을 가져갈지 고르는 것이 배낭 문제입니다.

이름의 0/1은 물건마다 선택지가 두 개뿐이라는 뜻입니다. 가져가면 1, 두고 가면 0이고, 물건 하나를 반만 넣거나 같은 물건을 두 개 넣는 일은 허용하지 않습니다. 물건이 n개면 경우의 수는 2의 n제곱입니다. 4개일 때는 16가지라 일일이 따져 볼 수 있지만, 40개만 돼도 1조 가지를 넘어서 전부 확인하는 방법은 쓸 수 없습니다. 그래서 작은 문제의 답을 표에 저장해 재사용하는 동적계획법이 필요해집니다.

입력과 출력을 정리하면 다음과 같습니다.

• 입력: 물건 n개 각각의 무게 w와 가치 v, 그리고 배낭의 용량 W
• 조건: 고른 물건의 무게 합은 W 이하, 물건은 통째로 하나씩만 선택
• 목표: 고른 물건의 가치 합을 최대로 만드는 조합 찾기

아래 예시로 보면 쉽습니다. 물건이 A(1kg, 가치 1), B(3kg, 4), C(4kg, 5), D(5kg, 7)이고 용량이 7kg일 때, 가능한 조합 중 B와 C를 함께 넣으면 무게 7kg에 가치 9로 가장 큽니다. 가치가 제일 큰 D를 고르면 남는 2kg에는 A밖에 못 넣어 가치 8에 그칩니다. 이렇게 “당장 좋아 보이는 물건”만 고르면 틀릴 수 있다는 점이 이 문제의 핵심입니다. 이 표를 어떻게 채우는지는 아래에서 단계별로 설명합니다.

동적계획법은 작은 문제의 답을 표에 저장해 큰 문제를 푸는 방법

정의: 동적계획법은 문제를 겹치는 부분 문제로 나누고 각 부분 문제의 답을 한 번만 계산해 저장(메모이제이션 또는 표 채우기)한 뒤 재사용하는 설계 기법입니다. 최적 부분 구조와 중복 부분 문제라는 두 조건이 있을 때 씁니다.

• 0/1 배낭 문제: 무게 w와 가치 v를 가진 n개 물건 중 일부를 골라, 무게 합이 W 이하이면서 가치 합이 최대가 되게 하는 문제. 물건은 통째로 넣거나(1) 넣지 않거나(0) 둘 중 하나입니다.

점화식 하나로 표 전체가 채워진다

dp[i][c] = 앞의 i개 물건만 고려하고 용량이 c일 때의 최대 가치

• i번째 물건 무게가 c보다 크면: dp[i][c] = dp[i-1][c] (넣을 수 없음)
• 아니면: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w_i] + v_i) (안 넣는 경우와 넣는 경우 중 큰 값)

예시: 용량 7kg 배낭에 물건 4개

물건은 A(1kg, 가치 1), B(3kg, 4), C(4kg, 5), D(5kg, 7)입니다.

표의 마지막 칸 dp[4][7] = 9가 최대 가치입니다. 어떤 물건을 골랐는지는 거꾸로 따라가며 찾습니다.

1. dp[4][7] = 9, dp[3][7] = 9로 같으므로 D는 넣지 않았다.
2. dp[3][7] = 9, dp[2][7] = 5로 다르므로 C를 넣었다. 남은 용량 7-4 = 3.
3. dp[2][3] = 4, dp[1][3] = 1로 다르므로 B를 넣었다. 남은 용량 0.

결과는 B + C, 무게 7kg, 가치 9입니다(코드로 검산). 가치가 가장 큰 D(7)를 먼저 넣으면 남은 2kg에 A만 들어가 가치 8에 그칩니다. 눈앞의 최선이 전체 최선이 아닌 사례입니다.

탐욕법이 통하는 분할 배낭과의 차이

구분	0/1 배낭	분할(Fractional) 배낭
물건 처리	통째로 넣거나 빼기	쪼개서 일부만 넣기 가능
최적 해법	동적계획법(또는 분기 한정)	단위 무게당 가치 순 탐욕법
복잡도	O(nW)	O(n log n), 정렬이 지배
문제 난이도	NP-난해(일반적으로)	다항 시간

O(nW)인데 왜 다항 시간이 아니라고 할까

표 크기가 물건 수 n과 용량 W의 곱이라 O(nW)입니다. 그런데 W는 값의 크기이지 입력 길이가 아닙니다. W를 표현하는 비트 수가 k라면 W는 2^k까지 커질 수 있어, 입력 길이 기준으로는 지수 시간입니다. 그래서 의사 다항 시간(Pseudo-polynomial)이라고 부릅니다. 서술형에서 이 구분을 쓰면 확실한 가점 포인트입니다.

답안에서 놓치기 쉬운 포인트

• 공간은 한 행만 유지하면 O(W)로 줄일 수 있습니다. 이때 용량을 큰 쪽에서 작은 쪽으로 갱신해야 같은 물건을 두 번 넣지 않습니다.
• 분할 정복과 DP의 차이는 부분 문제가 겹치느냐입니다. 겹치지 않으면 분할 정복, 겹치면 DP입니다.
• 설계 기법 비교(탐욕법, 분할 정복, DP, 백트래킹, 분기 한정)를 한 표로 정리해 두면 여러 문제에 재사용됩니다.

시험 직전 한 줄 요약

0/1 배낭은 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w]+v) 점화식의 동적계획법으로 O(nW)에 풀고, 물건을 쪼갤 수 있는 분할 배낭만 탐욕법으로 최적해가 보장됩니다.

학습용 정리이며 실제 시험 문항과 다를 수 있습니다. 출제 기준은 큐넷 공지를 확인하세요. 그림은 이해를 돕기 위한 개념도와 예시입니다.