[백준] JavaScript - 평범한 배낭 (12865)

개요

문제 이름: 평범한 배낭 (12865)
문제 링크: https://www.acmicpc.net/problem/12865
플랫폼: 백준
알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제
소요 시간: 5시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있는 대표적인 0-1 냅색 문제(Knapsack Problem) 혹은 배낭 문제 입니다. 냅색 문제는 제한된 용량의 가방(배낭)에 가치와 무게가 다른 물건들을 넣어 가방에 담을 수 있는 물건들의 가치합을 최대로 만드는 문제입니다.

 

0-1 냅색 문제는 각 물건을 가방에 담을지 안 담을지 두 가지 선택만 가능한 냅색 문제의 한 종류로, 동적 계획법의 대표적인 예시 문제 중 하나입니다.

 

이 문제에서 요구하는 것은 준서가 여행에 가져갈 물건을 선택하는 과정으로, 최대 K 무게만큼의 배낭에 N개의 물건들 중 가치의 합이 최대가 되도록 물건을 선택하는 것입니다.

 

동적 계획법의 아이디어는 부분 문제의 해답을 재활용하여 전체 문제의 해답을 구하는 것입니다. 0-1 냅색 문제를 동적 계획법으로 해결하는 방식은 아래와 같습니다.

1. dp[i][w]를 "i번째 물건까지 고려했을 때, 무게가 w이하인 가방에 넣을 수 있는 물건 가치의 최댓값"이라고 정의합니다.
2. N+1 행과 K+1 열을 가지는 2차원 DP 테이블(배열)을 생성하고 0으로 초기화합니다.
   1. 행은 고려하는 물건의 번호를 의미하며 0번째부터 N번째까지 존재합니다. (0번째 행은 물건을 하나도 고려하지 않은 상태를 의미)
   2. 열은 가방의 무게를 의미하며 0부터 K까지 존재합니다.
3. 1번 물건부터 N번 물건까지 차례대로 고려하면서 DP 테이블을 채워나갑니다.
   1. 현재 고려 중인 i번 물건의 무게가 w보다 작거나 같다면, i번 물건을 가방에 넣는 경우(dp[i-1][w-weight] + value)와 넣지 않는 경우(dp[i-1][w]) 중 가치합이 더 큰 값을 선택하여 dp[i][w]에 저장합니다.
   2. 현재 고려 중인 i번 물건의 무게가 w보다 크다면, i번 물건을 가방에 넣을 수 없으므로 이전 물건까지 고려한 최댓값 그대로 dp[i-1][w]를 dp[i][w]에 저장합니다.
4. dp[N][K]에 저장된 값이 최종 정답, 즉 배낭에 넣을 수 있는 물건들의 가치합의 최댓값이 됩니다.

 

이 문제에서는 아래와 같은 순서로 접근해야 합니다.

1. 입력으로 물품의 수 N과 무게 제한 K를 받습니다.
2. N개의 물건 각각의 무게 W와 가치 V를 입력받아 배열 혹은 객체에 저장합니다.
3. N+1 행과 K+1 열을 가지는 2차원 DP 테이블을 0으로 초기화합니다.
4. 1번 물건부터 N번 물건까지 차례로 고려하면서, 현재 물건을 넣는 경우와 넣지 않는 경우 중 가치합이 더 큰 값을 선택하여 DP 테이블을 갱신합니다.
5. DP 테이블 갱신이 모두 끝나면, dp[N][K]에 저장된 값이 배낭에 넣을 수 있는 물건들의 가치합의 최댓값이 되므로 이를 출력합니다.

 

 

배낭 문제(Knapsack Problem)

배낭 문제는 제한된 용량을 가진 배낭에 물건들을 담을 때, 가장 효율적으로 많이 담는 방법을 찾는 최적화 문제입니다. 쉽게 말해 "제한된 용량의 배낭에 어떤 물건들을 담아야 가장 큰 가치를 얻을 수 있을까?"를 해결하는 문제입니다.

 

실생활 예시로 이해하기

여행을 갈 때를 생각해보면 쉽습니다.

• 캐리어(배낭)의 무게 제한이 20kg입니다.
• 여행에 가져가고 싶은 물건들이 있습니다.
  • 노트북(2kg, 중요도 5)
  • 카메라(1.5kg, 중요도 4)
  • 옷(3kg, 중요도 3)
  • 책(1kg, 중요도 2) 기타 등등...
• 어떤 물건들을 담아야 가장 효율적일까요?

이것이 바로 배낭 문제의 실질적인 유형이라고 할 수 있습니다.

 

배낭 문제의 종류

0/1 배낭 문제 (0/1 Knapsack Problem)

• 각 물건을 통째로 하나만 선택하거나 선택하지 않는 경우
• 물건을 쪼갤 수 없음
• 예: 노트북, 책, 카메라 등 개별 물품을 넣거나 넣지 않는 선택

다중 배낭 문제 (Multiple Knapsack)

• 같은 물건을 여러 개 담을 수 있음
• 예: 같은 책을 여러 권 담을 수 있음

분할 가능 배낭 문제 (Fractional Knapsack Problem)

• 물건을 부분적으로 쪼개서 담을 수 있는 경우
• 예: 금, 곡물처럼 임의의 양만큼 나눌 수 있는 물품

무제한 배낭 문제 (Unbounded Knapsack Problem)

• 각 물건을 무제한으로 선택할 수 있는 경우
• 예: 동전 교환 문제

 

0/1 배낭 문제 설명

일상 속 배낭 문제

일단 비행기를 탄다고 가정합니다.

• 캐리어 무게 제한: 15kg
• 가져가고 싶은 물건들?
  • 노트북(2kg, 가치 500만원)
  • 옷(5kg, 가치 100만원)
  • 선물(4kg, 가치 50만원)
  • 책(3kg, 가치 30만원)
  • 화장품(2kg, 가치 80만원)

우리의 목표: 15kg 안에 가장 비싼 물건들을 담기!

 

이걸 어떻게 풀어야 할까?

 

일반적으로 생각하는 방법 (그리디)

"어? 그냥 비싼 거부터 넣으면 되는 거 아닌가?"

1. 노트북 (2kg, 500만원) → 넣기! (남은 무게: 13kg)
2. 옷 (5kg, 100만원) → 넣기! (남은 무게: 8kg)
3. 화장품 (2kg, 80만원) → 넣기! (남은 무게: 6kg)
4. 선물 (4kg, 50만원) → 넣기! (남은 무게: 2kg)
5. 책은 못 넣음...

총 가치: 730만원

 

더 좋은 방법이 있을까?

다른 조합을 생각해보면...

• 노트북 + 옷 + 선물 조합은?
• 노트북 + 화장품 + 책 조합은?
• 등등...

이렇게 가능한 모든 조합을 다 확인해봐야 진짜 최고의 답을 찾을 수 있습니다.

 

동적 계획법으로 풀기

단계 별로 생각합니다. 작은 무게부터 차근차근 생각해봅시다.

1. 1kg 가방이 있다면?
   • 아무것도 못 담음 (모든 물건이 1kg보다 무거움)
   • 최대 가치: 0원
2. 2kg 가방이 있다면?
   • 노트북(2kg) 또는 화장품(2kg) 중 선택 가능
   • 최대 가치: 500만원 (노트북 선택)
3. 3kg 가방이 있다면?
   • 노트북(2kg) 또는 화장품(2kg) 또는 책(3kg) 중 선택
   • 최대 가치: 500만원 (노트북 선택)

이런 식으로 무게를 하나씩 늘려가며 계산합니다.

 

실제 계산 과정 시각화

[가방 무게별 최대 가치 표]
무게(kg) │ 가능한 물건 조합    │ 최대 가치
─────────┼───────────────────┼──────────
1kg      │ (없음)            │ 0원
2kg      │ 노트북/화장품      │ 500만원
3kg      │ 노트북/화장품/책   │ 500만원
4kg      │ 노트북+화장품/선물 │ 580만원
5kg      │ 노트북+화장품/옷   │ 580만원
...
15kg     │ 최적의 조합       │ ???만원

 

DP 테이블 과정

각 단계별로 DP 테이블이 어떻게 채워지는지 표로 보여드리겠습니다.

4 7    (물건 4개, 최대 무게 7kg)
6 13   (1번 물건: 무게 6kg, 가치 13)
4 8    (2번 물건: 무게 4kg, 가치 8)
3 6    (3번 물건: 무게 3kg, 가치 6)
5 12   (4번 물건: 무게 5kg, 가치 12)

해당 물건들에 관한 예제입니다.

 

초기 상태 (0번째 행)

물건\무게	0	1	2	3	4	5	6	7
0번	0	0	0	0	0	0	0	0

• 아직 어떤 물건도 고려하지 않은 상태라서 모든 무게에서 가치가 0입니다.

 

1번 물건 고려 (무게 6, 가치 13)

물건\무게	0	1	2	3	4	5	6	7
0번	0	0	0	0	0	0	0	0
1번	0	0	0	0	0	0	13	13

• 무게 0~5: 1번 물건(무게 6)을 넣을 수 없으므로 이전 행과 동일한 0
• 무게 6: 처음으로 1번 물건을 넣을 수 있음. 이전 값(0) vs 1번 물건 가치(13) 중 큰 값 선택 → 13
• 무게 7: 1번 물건을 넣고 남은 무게(1)의 가치(0) + 1번 물건 가치(13) vs 이전 값(0) 중 큰 값 선택 → 13

 

2번 물건까지 고려 (무게 4, 가치 8)

물건\무게	0	1	2	3	4	5	6	7
0번	0	0	0	0	0	0	0	0
1번	0	0	0	0	0	0	13	13
2번	0	0	0	0	8	8	13	13

• 무게 0~3: 2번 물건(무게 4)을 넣을 수 없으므로 이전 행과 동일
• 무게 4: 2번 물건을 넣을 수 있음. 이전 값(0) vs 2번 물건 가치(8) 중 큰 값 선택 → 8
• 무게 5: 2번 물건을 넣고 남은 무게(1)의 가치(0) + 2번 물건 가치(8) vs 이전 값(0) 중 큰 값 선택 → 8
• 무게 6: 2번 물건을 넣고 남은 무게(2)의 가치(0) + 2번 물건 가치(8) = 8 vs 이전 값(13) 중 큰 값 선택 → 13
• 무게 7: 2번 물건을 넣고 남은 무게(3)의 가치(0) + 2번 물건 가치(8) = 8 vs 이전 값(13) 중 큰 값 선택 → 13

 

3번 물건까지 고려 (무게 3, 가치 6)

물건\무게	0	1	2	3	4	5	6	7
0번	0	0	0	0	0	0	0	0
1번	0	0	0	0	0	0	13	13
2번	0	0	0	0	8	8	13	13
3번	0	0	0	6	8	8	13	14

• 무게 0~2: 3번 물건(무게 3)을 넣을 수 없으므로 이전 행과 동일
• 무게 3: 3번 물건을 넣을 수 있음. 이전 값(0) vs 3번 물건 가치(6) 중 큰 값 선택 → 6
• 무게 4: 3번 물건을 넣고 남은 무게(1)의 가치(0) + 3번 물건 가치(6) = 6 vs 이전 값(8) 중 큰 값 선택 → 8
• 무게 5: 3번 물건을 넣고 남은 무게(2)의 가치(0) + 3번 물건 가치(6) = 6 vs 이전 값(8) 중 큰 값 선택 → 8
• 무게 6: 3번 물건을 넣고 남은 무게(3)의 가치(6) + 3번 물건 가치(6) = 12 vs 이전 값(13) 중 큰 값 선택 → 13
• 무게 7: 3번 물건을 넣고 남은 무게(4)의 가치(8) + 3번 물건 가치(6) = 14 vs 이전 값(13) 중 큰 값 선택 → 14

 

 

4번 물건까지 고려 (무게 5, 가치 12)

물건\무게	0	1	2	3	4	5	6	7
0번	0	0	0	0	0	0	0	0
1번	0	0	0	0	0	0	13	13
2번	0	0	0	0	8	8	13	13
3번	0	0	0	6	8	8	13	14
4번	0	0	0	6	8	12	13	14

• 무게 0~4: 4번 물건(무게 5)을 넣을 수 없으므로 이전 행과 동일
• 무게 5: 4번 물건을 넣을 수 있음. 이전 값(8) vs 4번 물건 가치(12) 중 큰 값 선택 → 12
• 무게 6: 4번 물건을 넣고 남은 무게(1)의 가치(0) + 4번 물건 가치(12) = 12 vs 이전 값(13) 중 큰 값 선택 → 13
• 무게 7: 4번 물건을 넣고 남은 무게(2)의 가치(0) + 4번 물건 가치(12) = 12 vs 이전 값(14) 중 큰 값 선택 → 14

테이블의 마지막 값 dp[4][7] = 14가 최종 답이 됩니다.

 

이런 식으로 단계별로 테이블이 채워지면서, 각 단계에서의 최적의 선택이 반영됩니다. 최종적으로 마지막 행, 마지막 열의 값인 14가 우리가 구하고자 하는 최대 가치가 됩니다.

 

실제 코드

const items = [
    {weight: 2, value: 500}, // 노트북
    {weight: 5, value: 100}, // 옷
    {weight: 4, value: 50},  // 선물
    {weight: 3, value: 30},  // 책
    {weight: 2, value: 80}   // 화장품
];

// 2차원 DP 테이블 생성
const dp = Array.from({length: items.length + 1}, () => Array(16).fill(0));

// 각 물건에 대해
for (let i = 1; i <= items.length; i++) {
    const item = items[i-1];
    // 각 무게에 대해
    for (let w = 1; w <= 15; w++) {
        if (item.weight > w) {
            // 현재 물건을 넣을 수 없는 경우
            dp[i][w] = dp[i-1][w];
        } else {
            // 현재 물건을 넣을 수 있는 경우
            dp[i][w] = Math.max(
                dp[i-1][w],                           // 안 넣는 경우
                dp[i-1][w - item.weight] + item.value // 넣는 경우
            );
        }
    }
}

 

추가 비유

우리가 옷장을 정리한다고 할 때...

1. 처음에는 작은 공간부터 시작
2. 공간이 커질수록 더 많은 옷을 넣을 수 있음
3. 각 공간마다 "이 옷을 넣을까? 말까?" 결정
4. 이전에 했던 결정들을 기억해두고 활용

배낭 문제도 똑같습니다!

1. 작은 무게부터 시작
2. 무게가 커질수록 더 많은 물건을 고려
3. 각 무게마다 "이 물건을 넣을까? 말까?" 결정
4. 이전 결정들을 표에 기록하고 활용

이렇게 차근차근 계산해나가면, 결국 우리가 원하는 최적의 답을 찾을 수 있습니다.

 

 

시도

1차 시도  (성공)

// 파일 시스템 모듈 불러오기
const fs = require('fs');

// 입력 파일 읽어와서 처리
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 줄에서 N과 K를 추출하고 숫자로 변환
const [N, K] = input[0].split(' ').map(Number);

// 나머지 줄에서 물건들의 정보를 추출
const items = input.slice(1).map(line => line.split(' ').map(Number));

// 메인 knapsack 함수 정의
function knapsack(N, K, items) {
    // DP 테이블 생성 및 0으로 초기화
    // N+1 행: 고려한 물건의 개수 (0개부터 N개까지)
    // K+1 열: 가능한 무게 (0부터 K까지)
    const dp = Array.from({length: N + 1}, () => Array(K + 1).fill(0));
    
    // 각 물건에 대해 반복
    for (let i = 1; i <= N; i++) {
        // 현재 물건의 무게와 가치
        const [weight, value] = items[i-1];
        
        // 각 가능한 무게에 대해 반복
        for (let w = 1; w <= K; w++) {
            // 현재 물건을 넣을 수 없는 경우
            if (weight > w) {
                // 이전 상태 그대로 유지
                dp[i][w] = dp[i-1][w];
            } else {
                // 현재 물건을 넣는 경우와 넣지 않는 경우 중 최댓값 선택
                dp[i][w] = Math.max(
                    dp[i-1][w],                    // 넣지 않는 경우
                    dp[i-1][w-weight] + value      // 넣는 경우
                );
            }
        }
    }
    
    // 최종 결과 반환
    return dp[N][K];
}

// 결과 출력
console.log(knapsack(N, K, items));

위 코드는 0-1 배낭 문제를 동적 계획법을 사용하여 해결합니다.

1. 먼저 입력을 받아 첫 줄에서 물건의 개수 N과 배낭의 최대 무게 K를 추출하고, 나머지 줄에서 각 물건의 무게와 가치를 items 배열에 저장합니다.
2. knapsack 함수에서는 (N+1) x (K+1) 크기의 DP 테이블(dp)을 생성하고 0으로 초기화합니다.
3. 이중 for 문을 통해 각 물건에 대해 모든 가능한 무게를 고려하면서 DP 테이블을 채웁니다.
   1. 현재 물건의 무게가 배낭의 무게보다 크면 이전 상태를 유지합니다.
   2. 물건을 넣을 수 있다면, 현재 물건을 넣는 경우와 넣지 않는 경우 중 최댓값을 선택하여 dp[i][w]에 저장합니다.
4. 모든 물건을 고려한 후, dp[N][K]에는 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값이 저장되므로 이를 반환합니다.
5. 최종적으로 knapsack 함수의 결과를 출력합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(N * K)
  • DP 테이블을 채우는 데 O(N * K)의 시간이 소요됩니다.
  • 각 물건(N개)에 대해 가능한 모든 무게(K개)를 확인하기 때문입니다.
• 공간 복잡도: O(N * K)
  • DP 테이블의 크기가 (N+1) x (K+1)이므로 O(N * K)의 공간이 필요합니다.

 

사용된 주요 메서드

• Array.from({length: N}, () => Array(M)): 길이가 N이고 각 요소가 길이 M의 배열로 초기화된 2차원 배열을 생성합니다.
• Array.fill(value): 배열의 모든 요소를 주어진 값(value)으로 채웁니다.
• Array.slice(start, end): 배열의 start 인덱스부터 end 인덱스 전까지의 요소를 새로운 배열로 반환합니다.
• String.split(separator): 문자열을 주어진 구분자(separator)로 나누어 배열로 반환합니다.
• Array.map(callback): 배열의 각 요소에 대해 주어진 콜백 함수를 실행하고, 그 결과를 모아 새로운 배열을 반환합니다.
• Math.max(a, b): 주어진 숫자 중 더 큰 값을 반환합니다.