동적 계획법(DP) 배낭 문제 (0-1 Knapsack 완벽해결)

알고리즘을 공부하는 수많은 개발자들을 좌절에 빠뜨리는 동적 계획법(Dynamic Programming, DP)의 가장 대표적이고 악명 높은 척도가 바로 '배낭 문제(Knapsack Problem)'입니다. 한밤중에 보석상에 침입한 도둑이 감당할 수 있는 최대 무게가 정해진 배낭을 메고 있을 때, 어떻게 보석들을 담아야 훔친 보석들의 총가치를 가장 높일 수 있을지에 대한 유명한 딜레마입니다. 이 문제는 단순한 탐욕법(Greedy)으로는 절대 풀 수 없는 치명적인 함정을 가지고 있습니다. 오늘은 동적 계획법의 정수라 불리는 '0-1 배낭 문제'의 2차원 배열 설계법과 점화식 도출 과정, 그리고 공간 복잡도를 획기적으로 줄이는 1차원 배열 최적화 기법까지 완벽하게 해부해 보겠습니다.

1. 0-1 배낭 문제(0-1 Knapsack)란 무엇인가?

배낭 문제는 보석을 자를 수 있느냐 없느냐에 따라 두 가지로 분류됩니다. 보석을 가루처럼 잘게 쪼개서 담을 수 있다면 '분할 가능 배낭 문제(Fractional Knapsack)'라고 부르며, 이는 무게 대비 가치가 가장 높은 것부터 욱여넣는 단순한 그리디(Greedy) 알고리즘으로 쉽게 해결됩니다. 하지만 현실의 금괴나 노트북처럼 물건을 쪼갤 수 없고 오직 '통째로 담거나(1), 아예 담지 않거나(0)' 두 가지 선택지만 존재하는 경우를 '0-1 배낭 문제'라고 부르며, 이는 오직 동적 계획법(DP)을 통해서만 최적해를 구할 수 있습니다.

1-1. 그리디 알고리즘이 실패하는 치명적 이유

배낭의 최대 수용 무게가 10kg이라고 가정해 봅시다. 눈앞에 A(무게 6kg, 가치 600만 원), B(무게 5kg, 가치 400만 원), C(무게 5kg, 가치 400만 원) 세 개의 물건이 있습니다.

• 그리디(탐욕적) 선택: 당장 눈앞에 가치가 가장 높은 A(600만 원)를 먼저 담습니다. 배낭에는 4kg의 여유 공간이 남습니다. 하지만 남은 B와 C는 모두 5kg이므로 더 이상 아무것도 담을 수 없습니다. 최종 가치는 600만 원입니다.
• 최적의 선택(DP): 가장 가치가 높은 A를 과감히 포기하고, B와 C를 담습니다. 5kg + 5kg = 10kg으로 배낭을 꽉 채우며, 최종 가치는 800만 원이 됩니다.

이처럼 무조건 비싼 것을 고르는 근시안적인 선택은 배낭의 '잔여 공간'을 비효율적으로 만들 수 있기 때문에, 배낭 문제는 모든 경우의 수와 잔여 용량을 체계적으로 기록하는 DP로 접근해야만 합니다.

2. 2차원 DP 테이블 설계와 점화식 도출

배낭 문제를 해결하는 핵심은 가로축을 '배낭의 현재 버틸 수 있는 임시 무게(1~K)'로 두고, 세로축을 '고려할 물건의 번호(1~N)'로 두는 2차원 배열 dp[i][w]를 그리는 것입니다. 이 배열의 값은 "i번째 물건까지 탐색했을 때, w 무게 한도 내에서 얻을 수 있는 최대 가치"를 의미합니다.

2-1. 마법의 점화식 (Recurrence Relation)

i번째 물건을 배낭에 넣을지 말지 고민하는 순간, 우리에게는 두 가지 선택지가 주어집니다.

1. 물건이 너무 무거워서 아예 배낭에 들어가지 않는 경우 (물건 무게 > 현재 버틸 수 있는 무게 w): 선택의 여지가 없습니다. 이 물건을 배낭에 넣지 못하므로, 최대 가치는 이전 물건(i-1)까지 고려했을 때의 최대 가치를 그대로 가져옵니다. dp[i][w] = dp[i-1][w]
2. 물건을 배낭에 넣을 수 있는 여유가 있는 경우: 여기서 딜레마가 발생합니다. "이 물건을 안 넣고 이전 상태를 유지하는 것"과, "이 물건을 넣기 위해 미리 배낭의 공간을 비워두었던 과거의 최적 상태에 현재 물건의 가치를 더하는 것" 중 어느 것이 더 이득인지 비교해야 합니다. dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - 물건무게] + 물건가치)

이 점화식을 통해 배열의 첫 번째 칸부터 마지막 칸까지 순차적으로 채워나가면, 최종적으로 dp[N][K] (모든 물건을 고려하고, 최대 무게를 꽉 채웠을 때) 칸에 우리가 원하는 완벽한 정답이 들어있게 됩니다. 시간 복잡도는 O(N*K)가 됩니다.

3. 메모리 최적화: 1차원 배열로의 압축

2차원 배열은 직관적이지만 물건의 개수와 무게가 커질수록 메모리(공간 복잡도)를 너무 많이 차지합니다. 점화식을 가만히 살펴보면, i번째 줄을 계산할 때는 오직 바로 윗줄인 i-1번째 줄의 데이터만 필요하다는 사실을 깨달을 수 있습니다. 따라서 2차원 배열을 1차원 배열 dp[w]로 압축할 수 있습니다.

// 1차원 배열을 활용한 0-1 배낭 문제 최적화 (Java)
int[] dp = new int[K + 1];

for (int i = 0; i < N; i++) {
  // 1차원 배열 압축 시에는 반드시 '뒤에서부터(K부터)' 탐색해야 합니다!
  for (int w = K; w >= weight[i]; w--) {
  	dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
  }
}

여기서 개발자들이 가장 많이 하는 치명적인 실수는 무게를 1부터 K까지 앞에서부터 갱신하는 것입니다. 앞에서부터 갱신하면 이번 턴에 방금 넣은 물건의 가치가 뒷부분 연산에 다시 중복 합산되어 '0-1(물건 하나당 1번)' 규칙이 깨지고 동일한 물건이 무한대로 들어가는 오류가 발생합니다. 따라서 반드시 뒤에서부터 역순으로(K -> 0) 갱신해야 1차원 배열 최적화가 완벽하게 동작합니다.

[핵심 요약] 1. 0-1 배낭 문제는 물건을 쪼갤 수 없는 상황에서 가치를 극대화하는 동적 계획법(DP)의 대표 문제입니다. 2. 2차원 배열을 사용하여 dp[i][w] = max(이전 가치, 남은 무게의 최대 가치 + 현재 가치) 점화식을 도출합니다. 3. 메모리 절약을 위해 1차원 배열로 최적화할 수 있으며, 이 경우 물건 중복 방지를 위해 반드시 역순(뒤에서부터)으로 순회해야 합니다.