[알고리즘 Deep Dive #3] 배낭 문제(Knapsack): 0/1, 분할, 변형까지 완전 정복

들어가며

알고리즘을 공부하다 보면 거의 반드시 만나게 되는 문제가 하나 있다.
바로 Knapsack Problem(배낭 문제)다.

이 문제는 동적 프로그래밍(DP)을 설명할 때 가장 자주 등장하는 예제이기도 하고,
실제 코딩 테스트에서도 다양한 형태로 변형되어 자주 출제된다.

문제의 설정은 매우 단순하다.

무게 제한이 있는 배낭에 물건들을 담아 가장 높은 가치를 만들자.

예를 들어 이런 상황을 생각해 보자.

• 배낭이 하나 있고
• 배낭은 최대 50kg까지 담을 수 있다
• 우리 앞에는 여러 개의 물건이 있다

각 물건에는 두 가지 정보가 있다.

• 무게 (weight)
• 가치 (value)

이제 우리는 다음 질문에 답해야 한다.

어떤 물건을 선택해야 배낭의 총 가치가 최대가 될까?

겉보기에는 단순해 보이지만, 이 문제는 어떤 선택 규칙을 적용하느냐에 따라 완전히 다른 알고리즘이 필요하다.

특히 다음 질문이 중요하다.

물건을 쪼개서 담을 수 있는가?

이 조건 하나 때문에 문제는 두 가지로 나뉜다.

1. 0/1 배낭 문제
   • 물건을 통째로만 넣을 수 있다
   • 넣거나 / 안 넣거나
2. 분할 배낭 문제
   • 물건을 쪼개서 넣을 수 있다

흥미로운 점은 여기 있다.

• 하나는 Dynamic Programming으로 풀고
• 하나는 Greedy Algorithm으로 푼다.

같은 “배낭 문제”인데 알고리즘이 완전히 달라지는 것이다.

이 글에서는 다음 세 가지를 차례대로 정리해 보겠다.

• 0/1 배낭 문제 (DP)
• 분할 배낭 문제 (Greedy)
• 실전에서 등장하는 배낭 문제의 변형

배낭 문제를 제대로 이해하면 DP 문제를 보는 눈이 크게 좋아진다.

---

배낭 문제란?

배낭 문제는 다음과 같은 상황을 모델링한 알고리즘 문제다.

무게 제한이 있는 배낭에 물건들을 담아 총 가치를 최대화하라.

좀 더 구체적으로 보자.

우리는 다음과 같은 정보를 가지고 있다.

• N개의 물건
• 배낭의 최대 무게 W

그리고 각 물건은 두 가지 값을 가진다.

• weight (무게)
• value (가치)

예를 들어 이런 상황이다.

배낭 최대 무게: 50

물건
A: 무게 10, 가치 60
B: 무게 20, 가치 100
C: 무게 30, 가치 120

이때 우리가 해야 할 일은 간단하다.

무게 제한을 넘지 않으면서 총 가치를 최대화하는 물건 조합을 찾는 것

예를 들어 다음과 같은 선택이 가능하다.

A + B = 무게 30, 가치 160
B + C = 무게 50, 가치 220
A + C = 무게 40, 가치 180

이 경우 가장 좋은 선택은

B + C = 가치 220

이다.

---

왜 어려운 문제일까?

물건이 3개일 때는 모든 경우를 직접 확인할 수 있다.

하지만 물건이 100개라면 이야기가 달라진다.

각 물건은 두 가지 선택이 가능하다.

• 넣는다
• 넣지 않는다

따라서 가능한 경우의 수는

2^N

이 된다.

예를 들어

• N = 30 → 약 10억 가지
• N = 100 → 사실상 계산 불가능

즉 모든 경우를 직접 탐색하는 방법은 사용할 수 없다.

그래서 이 문제에서는 문제의 구조를 이용한 알고리즘이 필요하다.

---

배낭 문제의 핵심 분기

배낭 문제를 풀 때 가장 먼저 확인해야 할 질문은 이것이다.

물건을 쪼갤 수 있는가?

이 질문 하나로 알고리즘이 완전히 달라진다.

경우	특징	알고리즘
물건을 쪼갤 수 없음	물건을 통째로만 선택	Dynamic Programming
물건을 쪼갤 수 있음	일부만 담을 수 있음	Greedy

다음 섹션에서는 먼저 0/1 배낭 문제를 살펴보자.
이 문제는 동적 프로그래밍의 대표적인 예제로 유명하다.

---

1. 0/1 배낭 문제 (Dynamic Programming)

0/1 배낭 문제에서는 각 물건을 쪼갤 수 없다.

즉 선택은 두 가지뿐이다.

• 넣는다 (1)
• 넣지 않는다 (0)

그래서 이름이 0/1 배낭 문제다.

---

직관적으로 생각해 보기

다음 상황을 보자.

배낭 최대 무게: 50

물건
A: 무게 10, 가치 60
B: 무게 20, 가치 100
C: 무게 30, 가치 120

가능한 조합을 생각해 보면 다음과 같다.

A + B = 무게 30, 가치 160
A + C = 무게 40, 가치 180
B + C = 무게 50, 가치 220

이 경우 최적 선택은

B + C = 가치 220

이다.

하지만 물건이 많아지면 이런 식으로 모든 조합을 직접 확인하는 것은 불가능하다.

---

그리디로 풀 수 있을까?

직관적으로 이런 생각을 할 수 있다.

가치 / 무게 비율이 높은 물건부터 담자

예를 들어 다음과 같은 데이터가 있다고 하자.

W = 50

물건:    A     B     C
무게:   10    20    30
가치:   60    100   120
비율:   6     5     4

비율 기준으로 정렬하면

A → B → C

그래서 그리디 선택은

A + B = 가치 160

이다.

하지만 실제 최적해는

B + C = 가치 220

이다.

즉 가치/무게 비율 기준 그리디 전략은 항상 최적을 보장하지 않는다.

이 문제에서는 물건의 조합이 결과에 영향을 주기 때문이다.

---

그래서 Dynamic Programming을 사용한다

0/1 배낭 문제의 핵심 아이디어는 다음이다.

일부 물건만 고려한 작은 문제를 먼저 해결하고,
그 결과를 이용해 더 큰 문제를 해결한다.

예를 들어 이런 질문을 만든다.

“앞에서 i개의 물건만 고려했을 때, 무게 w로 만들 수 있는 최대 가치는?”

이 값을 다음과 같이 정의한다.

dp[i][w]

의미:

dp[i][w] =
i번째 물건까지 고려했을 때
무게 w 이하로 담을 수 있는 최대 가치

이제 이 정의를 이용하면 점화식을 만들 수 있다.

---

점화식 만들기 (DP의 핵심)

앞에서 우리는 다음과 같이 정의했다.

dp[i][w] =
i번째 물건까지 고려했을 때
무게 w 이하로 담을 수 있는 최대 가치

이제 i번째 물건을 어떻게 처리할지 생각해 보자.

i번째 물건에는 두 가지 선택이 있다.

1. i번째 물건을 넣지 않는다
2. i번째 물건을 넣는다

이 두 경우를 각각 살펴보자.

---

1️⃣ 물건을 선택하지 않는 경우

i번째 물건을 선택하지 않으면
문제는 사실 i-1번째 물건까지만 고려한 문제와 동일하다.

따라서 값은 그대로 이어진다.

dp[i][w] = dp[i-1][w]

---

2️⃣ 물건을 선택하는 경우

이번에는 i번째 물건을 넣는 경우를 생각해 보자.

만약 이 물건의 무게가 weight[i]라면
배낭에는 그만큼 공간이 줄어든다.

즉 남은 무게는

w - weight[i]

가 된다.

그리고 i번째 물건의 가치를 추가한다.

따라서 값은 다음과 같다.

dp[i-1][w - weight[i]] + value[i]

---

두 선택 중 더 좋은 것을 고른다

우리는 항상 가치를 최대화해야 한다.

그래서 두 경우 중 더 큰 값을 선택한다.

dp[i][w] = max(
    dp[i-1][w],
    dp[i-1][w - weight[i]] + value[i]
)

이것이 바로 0/1 배낭 문제의 점화식이다.

---

직관적으로 이해하기

이 점화식이 의미하는 것은 사실 단순하다.

“이 물건을 넣는 것이 더 이득인가?”

• 넣지 않는 경우
• 넣는 경우

이 두 가지를 비교해서 더 가치가 높은 선택을 한다.

이 과정을 모든 물건과 모든 무게에 대해 반복하면
최종적으로 우리가 원하는 답을 얻을 수 있다.

---

공간 최적화 (1D DP)

앞에서 만든 2차원 DP는 이해하기 쉽지만 한 가지 단점이 있다.

dp 배열의 크기가 다음과 같다는 것이다.

O(N × W)

예를 들어

• 물건이 1000개
• 최대 무게가 100000

이라면 배열이 1억 칸이 된다.

그래서 실제 알고리즘 문제에서는 이 DP를 1차원 배열로 최적화하는 경우가 많다.

---

왜 1차원 배열로 줄일 수 있을까?

우리가 사용한 점화식을 다시 보자.

dp[i][w] = max(
    dp[i-1][w],
    dp[i-1][w-weight] + value
)

여기서 중요한 점이 하나 있다.

현재 행(i)은 오직 이전 행(i-1)만 참조한다.

즉 우리가 필요한 정보는 사실

• 현재 결과
• 이전 결과

뿐이다.

그래서 dp[i][w] 대신 하나의 배열 dp[w]만 사용해도 된다.

---

1D DP 구현

dp = [0] * (W + 1)

for weight, value in items:
    for w in range(W, weight - 1, -1):
        dp[w] = max(
            dp[w],
            dp[w - weight] + value
        )

print(dp[W])

여기서 핵심은 순회 방향이다.

for w in range(W, weight - 1, -1)

즉 뒤에서 앞으로 순회한다.

---

왜 역순으로 순회할까?

만약 정방향으로 순회하면 문제가 생긴다.

예를 들어 다음 코드라고 해 보자.

for w in range(weight, W + 1):
    dp[w] = max(dp[w], dp[w - weight] + value)

이렇게 하면 dp[w-weight] 값이 이미 이번 물건으로 갱신된 값일 수 있다.

즉 같은 물건을 여러 번 사용하는 결과가 된다.

예를 들어

물건 A를 두 번 사용

하는 상황이 생길 수 있다.

하지만 0/1 배낭 문제에서는 물건을 한 번만 사용할 수 있다.

그래서 이를 방지하기 위해 뒤에서 앞으로 순회해야 한다.

이렇게 하면 dp[w-weight]는 항상 이전 단계의 값을 유지하게 된다.

---

정리

0/1 배낭 DP 구현에는 두 가지 방식이 있다.

방식	공간	특징
2D DP	O(NW)	이해하기 쉽다
1D DP	O(W)	메모리를 크게 절약

실제 알고리즘 문제에서는 대부분 1D DP 방식을 사용한다.

---

2. 분할 배낭 (Greedy)

앞에서 본 0/1 배낭 문제에서는 물건을 쪼갤 수 없었다.

그래서 선택은 항상 두 가지였다.

• 넣는다
• 넣지 않는다

이 때문에 물건 조합을 고려해야 했고,
그래서 Dynamic Programming이 필요했다.

하지만 이제 상황이 조금 달라진다.

---

물건을 쪼갤 수 있다면?

이번에는 물건을 부분적으로 나눌 수 있다고 가정해 보자.

예를 들어 이런 상황이다.

배낭 최대 무게: 50

물건
A: 무게 10, 가치 60
B: 무게 20, 가치 100
C: 무게 30, 가치 120

만약 배낭 공간이 부족하다면
물건을 일부만 담는 것도 가능하다.

예를 들어

C 물건의 절반만 담기

같은 선택이 가능하다.

이런 문제를 분할 배낭(Fractional Knapsack) 이라고 한다.

---

핵심 아이디어

이 문제에서는 아주 직관적인 전략이 통한다.

가치 대비 무게가 높은 물건부터 담는다

즉 다음 값을 기준으로 정렬한다.

value / weight

이 값이 클수록 같은 무게로 더 많은 가치를 얻을 수 있다.

예를 들어 위 예시를 계산해 보면 다음과 같다.

물건    무게    가치    가치/무게
A       10      60        6
B       20      100       5
C       30      120       4

따라서 선택 순서는 다음과 같다.

A → B → C

---

실제 선택 과정

배낭 크기가 50이라면 다음처럼 담을 수 있다.

A (10kg) → 가치 60
B (20kg) → 가치 100
남은 공간 = 20

이제 C 물건은 무게가 30이지만
배낭에는 20만 남아 있다.

하지만 이 문제에서는 물건을 쪼갤 수 있다.

그래서 다음 선택이 가능하다.

C의 2/3만 담기

그러면 얻는 가치는

120 × (20 / 30) = 80

따라서 총 가치는

60 + 100 + 80 = 240

이 된다.

---

구현

이 알고리즘은 매우 간단하다.

1. 물건을 value / weight 기준으로 정렬
2. 가능한 만큼 배낭에 담기
3. 공간이 부족하면 일부만 담기

n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

items.sort(key=lambda x: x[1] / x[0], reverse=True)

total_value = 0.0

for weight, value in items:
    if W <= 0:
        break

    if W >= weight:
        total_value += value
        W -= weight
    else:
        total_value += value * (W / weight)
        W = 0

print(total_value)

---

왜 여기서는 그리디가 통할까?

핵심 이유는 하나다.

물건을 쪼갤 수 있기 때문이다.

그래서 항상 가치 밀도가 높은 것부터 채우는 전략이
전체 최적해로 이어진다.

반면 0/1 배낭 문제에서는 물건을 쪼갤 수 없기 때문에
이 전략이 실패할 수 있다.

---

0/1 배낭 vs 분할 배낭

문제	특징	해결 방법
0/1 배낭	물건을 쪼갤 수 없음	Dynamic Programming
분할 배낭	물건을 쪼갤 수 있음	Greedy

---

이제 배낭 문제의 두 가지 기본 형태를 모두 살펴봤다.

하지만 실제 알고리즘 문제에서는 배낭 문제가 조금 다른 형태로 변형되어 등장하는 경우가 많다.

다음 섹션에서는 실제 코딩 테스트에서 유명한 배낭 문제의 변형을 살펴보자.

---

3. 배낭 문제 변형 (BOJ 7579)

지금까지 본 배낭 문제는 비교적 전형적인 형태였다.

하지만 실제 알고리즘 문제에서는 배낭 구조가 조금 변형된 형태로 등장하는 경우가 많다.

대표적인 예가 바로 BOJ 7579 – 앱 문제다.

---

문제 상황

스마트폰에서 여러 개의 앱이 실행 중이라고 생각해 보자.

각 앱은 다음 두 가지 정보를 가진다.

• 사용 중인 메모리 (mᵢ)
• 앱을 비활성화하는 비용 (cᵢ)

우리는 어떤 앱들을 종료해서 최소 M 이상의 메모리를 확보해야 한다.

단, 앱을 종료할 때마다 비용이 발생한다.

그래서 목표는 다음과 같다.

M 이상의 메모리를 확보하면서 비용의 합을 최소화하라.

---

왜 배낭 문제일까?

이 문제를 조금만 바꿔서 생각해 보자.

앱 문제	배낭 문제
메모리 확보	가치
종료 비용	무게
비용 최소	무게 제한

즉 구조는 사실 거의 같다.

하지만 한 가지 차이가 있다.

일반적인 배낭 문제는 다음과 같다.

무게 제한 안에서
가치를 최대화

하지만 이 문제는 반대다.

가치(메모리) 하한을 만족하면서
비용을 최소화

즉 최적화 방향이 뒤집혀 있다.

---

DP 상태 설계

이 문제에서는 다음처럼 상태를 정의한다.

dp[j] = 비용 j로 확보할 수 있는 최대 메모리

즉 인덱스를 비용으로 설정한다.

왜냐하면 문제의 목표가

비용을 최소화하는 것

이기 때문이다.

---

왜 비용을 인덱스로 할까?

문제의 제한을 보면 이유가 명확해진다.

메모리 최대: 10,000,000
비용 최대: 10,000

만약 메모리를 인덱스로 사용하면

dp[10,000,000]

같은 거대한 배열이 필요하다.

하지만 비용을 인덱스로 쓰면

dp[10,000]

정도로 충분하다.

그래서 DP에서는 상태 크기를 줄이는 방향으로 인덱스를 선택하는 것이 중요하다.

---

구현

구조는 사실 0/1 배낭과 거의 동일하다.

import sys
input = sys.stdin.readline

n, M = map(int, input().split())
memory = list(map(int, input().split()))
cost = list(map(int, input().split()))

max_cost = sum(cost)
dp = [0] * (max_cost + 1)

for i in range(n):
    for j in range(max_cost, cost[i] - 1, -1):
        dp[j] = max(
            dp[j],
            dp[j - cost[i]] + memory[i]
        )

print(min(j for j in range(max_cost + 1) if dp[j] >= M))

---

핵심 아이디어

이 문제에서 중요한 것은 다음 두 가지다.

1️⃣ DP 상태 설계

dp[j] = 비용 j로 얻을 수 있는 최대 메모리

2️⃣ 역순 순회

for j in range(max_cost, cost[i]-1, -1)

이는 0/1 배낭 구조이기 때문이다.

---

배낭 문제에서 가장 중요한 것

배낭 문제를 풀 때 가장 중요한 질문은 항상 이것이다.

무엇을 인덱스로 둘 것인가?

즉 다음을 구분해야 한다.

• 제한 조건
• 최적화 대상

이 두 가지를 바탕으로 DP 상태를 설계하면
대부분의 배낭 변형 문제를 해결할 수 있다.

---

정리

배낭 문제는 알고리즘에서 매우 자주 등장하는 패턴이다.
겉보기에는 단순해 보이지만 문제의 조건에 따라 사용하는 알고리즘이 달라진다.

핵심은 다음 질문 하나다.

물건을 쪼갤 수 있는가?

이 질문에 따라 접근 방법이 달라진다.

문제 유형	특징	해결 방법
0/1 배낭	물건을 쪼갤 수 없음	Dynamic Programming
분할 배낭	물건을 쪼갤 수 있음	Greedy

---

배낭 문제 접근 방법

배낭 문제를 만났을 때는 다음 순서로 생각하면 된다.

1️⃣ 물건을 쪼갤 수 있는지 확인

가능 → Fractional Knapsack → Greedy
불가능 → 0/1 Knapsack → DP

---

2️⃣ DP 상태 정의

0/1 배낭에서는 보통 다음 형태를 사용한다.

dp[i][w]
= i번째 물건까지 고려했을 때
  무게 w로 만들 수 있는 최대 가치

또는 공간 최적화 버전

dp[w]
= 무게 w에서 얻을 수 있는 최대 가치

---

3️⃣ 역순 순회 확인

0/1 배낭에서는 같은 물건을 여러 번 사용하는 것을 막기 위해
반드시 뒤에서 앞으로 순회해야 한다.

for w in range(W, weight-1, -1):
    dp[w] = max(dp[w], dp[w-weight] + value)

---

기억해야 할 핵심

배낭 문제는 다양한 변형으로 등장하지만
대부분 다음 세 가지 중 하나로 해결된다.

1. 0/1 Knapsack (DP)
2. Fractional Knapsack (Greedy)
3. Knapsack Variant (DP 상태 재설계)

즉 문제에서

• 무엇이 제한 조건인지
• 무엇을 최적화해야 하는지

이 두 가지를 정확히 파악하면
배낭 문제의 대부분을 해결할 수 있다.

---

마무리

배낭 문제는 단순한 알고리즘 문제가 아니라
문제를 어떻게 모델링하고 상태를 설계하는지를 연습하기 좋은 문제다.

특히 Dynamic Programming을 처음 제대로 이해하는 데 매우 중요한 문제이기도 하다.

DP 문제를 풀다 보면 배낭 문제의 아이디어가
다른 문제들에서도 계속 등장한다.

그래서 배낭 문제를 확실히 이해해 두면
많은 DP 문제들이 훨씬 쉽게 보이기 시작한다.

---

Tags

#Algorithm #DP #DynamicProgramming #Knapsack #Greedy #Python #AlgorithmStudy