[코딩 테스트] 2026-04-26 — 0/1 배낭 문제

오늘의 문제 선정 이유

 

물류 최적화와 자원 배분에 대한 관심이 높아진 오늘, 제한된 용량 안에서 최대 이득을 고르는 0/1 배낭 문제는 가장 실전적인 DP 유형입니다.

문제 설명

한 물류 스타트업은 하루 한 번만 출발하는 배송 차량에 긴급 요청 박스를 실어야 합니다.
차량은 최대 Wkg까지만 실을 수 있습니다.

박스는 총 N개가 있습니다. 각 박스는 다음 두 값을 가집니다.

• weight[i]: 박스의 무게

 

• value[i]: 박스를 실었을 때 얻는 우선순위 점수

각 박스는 최대 한 번만 실을 수 있습니다.
차량의 무게 제한 W를 넘지 않으면서, 실은 박스들의 value 합이 최대가 되도록 하세요.

최대 점수를 출력하는 함수를 작성하세요.

입출력 예시

[text]입력: N = 4, W = 7
items = [(6, 13), (4, 8), (3, 6), (5, 12)]
출력: 14
설명: 무게 4, 3인 박스를 고르면 총 무게는 7, 총 점수는 14가 된다.

[text]입력: N = 5, W = 10
items = [(2, 4), (3, 7), (5, 10), (6, 13), (4, 8)]
출력: 21
설명: 무게 6, 4인 박스를 고르면 총 무게는 10, 총 점수는 21이다.

[text]입력: N = 3, W = 5
items = [(6, 20), (7, 30), (8, 40)]
출력: 0
설명: 어떤 박스도 담을 수 없다.

제약 조건

• 1 <= N <= 100

 

• 1 <= W <= 100000

 

• 1 <= weight[i] <= W 또는 weight[i] > W일 수도 있음

 

• 1 <= value[i] <= 10000

 

• 시간 제한: 2초

 

• 추가 메모리는 실무 코딩 테스트 수준에서 허용된다고 가정

풀이 접근법

핵심 아이디어

이 문제는 각 박스를 넣을지 말지 두 선택만 있는 전형적인 0/1 배낭 문제입니다.
완전 탐색으로 풀면 경우의 수가 2^N이라 너무 큽니다. 그래서 현재까지 고려한 박스들로, 특정 무게 한도에서 만들 수 있는 최대 가치를 저장하는 DP가 적합합니다.

단계별 풀이 과정

1. dp[w]를 무게 한도가 w일 때 얻을 수 있는 최대 가치로 정의합니다.
2. 박스를 하나씩 보면서, 해당 박스를 넣을 수 있는 무게 구간을 갱신합니다.
3. 이때 같은 박스를 여러 번 쓰면 안 되므로, 무게를 큰 쪽에서 작은 쪽으로 거꾸로 순회합니다.
4. dp[w] = max(dp[w], dp[w - weight] + value)로 갱신합니다.
5. 모든 박스를 처리한 뒤 dp[W]가 정답입니다.

코드 풀이

Python

 

[python]def solution(N, W, items):
    # dp[w] = 무게 한도가 w일 때 만들 수 있는 최대 가치
    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)

    return dp[W]


# 예시 실행
if __name__ == "__main__":
    N = 4
    W = 7
    items = [(6, 13), (4, 8), (3, 6), (5, 12)]
    print(solution(N, W, items))  # 14

JavaScript

 

[javascript]function solution(N, W, items) {
  // dp[w] = 무게 한도가 w일 때 만들 수 있는 최대 가치
  const dp = Array(W + 1).fill(0);

  for (const [weight, value] of items) {
    // 같은 아이템을 여러 번 쓰지 않기 위해 뒤에서부터 갱신
    for (let w = W; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }

  return dp[W];
}

// 예시 실행
const N = 4;
const W = 7;
const items = [
  [6, 13],
  [4, 8],
  [3, 6],
  [5, 12],
];

console.log(solution(N, W, items)); // 14

시간·공간 복잡도

• 시간 복잡도: O(N * W) — 각 박스마다 모든 무게 상태를 한 번씩 확인한다.

 

• 공간 복잡도: O(W) — 1차원 DP 배열 하나만 사용한다.

틀리기 쉬운 포인트

• 무게를 작은 쪽에서 큰 쪽으로 순회하면 같은 박스를 여러 번 사용하는 문제가 생깁니다. 0/1 배낭에서는 반드시 뒤에서 앞으로 갱신해야 합니다.

 

• dp[W]만 보는 것이 맞는지 헷갈릴 수 있습니다. 이 문제는 W 이하에서 최대 가치가 누적되도록 갱신되므로 dp[W]가 정답입니다.

 

• 어떤 박스의 무게가 W보다 크면 담을 수 없습니다. 하지만 별도 예외 처리 없이 반복문 조건으로 자연스럽게 걸러집니다.

유사 문제 패턴

• 예산 제한 내 최대 만족도 선택 문제: 비용이 weight, 만족도가 value로 바뀐 같은 구조입니다.

 

• 제한 시간 내 최대 점수 공부 계획 문제: 공부 주제별 소요 시간과 점수가 주어질 때 같은 DP를 적용할 수 있습니다.

 

• 디스크 용량 내 최대 중요 파일 백업 문제: 파일 크기와 중요도를 기준으로 선택하는 형태로 바꿔도 동일합니다.