5-8. DP: Knapsack Problem (0/1 배낭 문제) - 심화

1. 0/1 배낭 문제 복습

0/1 배낭 문제는 동적 프로그래밍(DP)을 사용하여 해결하는 대표적인 최적화 문제입니다. 주어진 배낭의 용량을 초과하지 않으면서, 배낭에 담을 수 있는 물건들의 가치의 합이 최대가 되도록 하는 것이 목표입니다. 각 물건은 배낭에 넣거나 넣지 않거나, 두 가지 선택지만 존재한다는 점에서 0/1 배낭 문제라고 불립니다.

배낭 문제의 기본적인 정의는 다음과 같습니다.

• 입력:
  • n: 물건의 수
  • W: 배낭의 용량
  • weights: 각 물건의 무게를 담은 배열 ( weights[i] 는 i번째 물건의 무게 )
  • values: 각 물건의 가치를 담은 배열 ( values[i] 는 i번째 물건의 가치 )
• 출력: 배낭에 담을 수 있는 물건들의 최대 가치

2. 0/1 배낭 문제의 기본적인 DP 해결법

0/1 배낭 문제를 DP로 해결하는 기본적인 방법은 2차원 배열을 사용하는 것입니다. dp[i][w]는 처음 i개의 물건을 고려했을 때, 무게 w를 초과하지 않도록 배낭에 담았을 때의 최대 가치를 의미합니다.

• 점화식:

  dp[i][w] = max( dp[i-1][w], // i번째 물건을 담지 않는 경우 dp[i-1][w - weights[i-1]] + values[i-1] // i번째 물건을 담는 경우 (단, w >= weights[i-1]) )

  • dp[i-1][w]: 이전 i-1개의 물건만 고려했을 때, 무게 w를 초과하지 않는 최대 가치
  • dp[i-1][w - weights[i-1]] + values[i-1]: 이전 i-1개의 물건 중, w - weights[i-1] 무게를 초과하지 않도록 담고, 현재 i번째 물건을 추가했을 때의 가치

• 초기 조건: dp[0][w] = 0 (어떤 물건도 고려하지 않았을 때, 어떤 무게 제한에서도 가치는 0)

• 결과: dp[n][W] (모든 물건을 고려했을 때, 배낭 용량 W에서의 최대 가치)

이 방법은 간단하고 직관적이지만, O(nW)의 시간 복잡도와 공간 복잡도를 가집니다. 여기서 n은 물건의 수, W는 배낭의 용량입니다.

3. 공간 복잡도 최적화: 1차원 배열 사용

위에서 설명한 기본적인 DP 해결법은 2차원 배열을 사용하므로, O(nW)의 공간 복잡도를 갖습니다. 하지만, 우리는 이전 행의 값만 참조하여 현재 행의 값을 계산할 수 있습니다. 따라서, 2차원 배열 대신 1차원 배열을 사용하여 공간 복잡도를 O(W)로 줄일 수 있습니다.

• 1차원 배열 dp[w]: 무게 w를 초과하지 않도록 물건을 담았을 때의 최대 가치

• 점화식 (수정):

  for i from 1 to n: for w from W to weights[i-1] (거꾸로 순회): dp[w] = max(dp[w], dp[w - weights[i-1]] + values[i-1])

  • 주의: w를 W에서 weights[i-1]까지 거꾸로 순회해야 합니다. 만약 w를 앞에서부터 순회하면, 이전에 계산된 dp[w - weights[i-1]] 값이 현재 물건을 포함한 결과일 수 있습니다. 이렇게 되면, 하나의 물건을 여러 번 담는 "무한 배낭 문제"와 같은 결과가 발생합니다. 0/1 배낭 문제에서는 각 물건을 한 번만 사용할 수 있어야 하므로, 거꾸로 순회해야 합니다.

• 초기 조건: dp[w] = 0 (모든 w에 대해)
• 결과: dp[W] (배낭 용량 W에서의 최대 가치)

위의 그림은 2차원 배열을 1차원 배열로 최적화하는 과정을 보여줍니다. 2차원 배열에서 이전 행의 값들을 참조하여 현재 행의 값을 계산하는 대신, 1차원 배열에서 거꾸로 순회하며 값을 업데이트함으로써 공간을 절약할 수 있습니다.

4. 다양한 변형 문제

0/1 배낭 문제는 다양한 형태로 변형될 수 있습니다. 이러한 변형 문제들은 문제 해결 능력을 향상시키기 위한 좋은 연습 문제입니다.

1) 제한된 개수의 물건 (Bounded Knapsack)

각 물건이 여러 개 주어질 수 있지만, 그 개수가 제한되어 있는 경우입니다. 이 경우, 각 물건의 개수를 count라고 할 때, 각 물건을 count번까지 반복하여 0/1 배낭 문제를 풀 수 있습니다.

• 점화식: 기존 0/1 배낭 문제와 동일하지만, 각 물건을 여러 번 고려해야 합니다.
• 구현: 각 물건에 대해 count번 반복하는 루프를 추가합니다.

2) 무한 개수의 물건 (Unbounded Knapsack)

각 물건이 무한히 많이 주어져 있는 경우입니다. 이 문제는 0/1 배낭 문제와는 다른 방식으로 해결됩니다.

• 점화식:

  dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) // w를 앞에서부터 순회

  • 0/1 배낭 문제와 달리, w를 앞에서부터 순회합니다. 이는 각 물건을 여러 번 사용할 수 있기 때문입니다.
  • 구현: 1차원 DP 테이블을 사용하며, 각 물건을 여러 번 사용할 수 있도록 합니다.

3) 여러 개의 배낭 (Multiple Knapsacks)

여러 개의 배낭이 주어지고, 각 물건을 여러 배낭에 분할하여 넣을 수 있는 경우입니다.

• 점화식: 각 배낭에 대해 개별적으로 0/1 배낭 문제를 풀고, 그 결과를 조합합니다.
• 구현: 각 배낭에 대해 DP를 수행하고, 모든 배낭의 결과를 합산합니다.

4) 최소 무게 제한 (Minimum Weight Constraint)

배낭에 담긴 물건들의 최소 무게를 만족해야 하는 경우입니다.

• 점화식: 무게가 최소 무게보다 작으면 해당 가치를 0으로 설정합니다.
• 구현: DP 과정에서 최소 무게 제한을 고려합니다.

5. 최적화 기법

0/1 배낭 문제를 더 빠르게 해결하기 위한 몇 가지 최적화 기법이 있습니다.

1) 정렬 (Sorting)

물건들을 가치/무게 비율 (values[i] / weights[i]) 기준으로 정렬하면, 일부 경우에 불필요한 계산을 줄일 수 있습니다. 가치/무게 비율이 높은 물건부터 고려하면, 더 큰 가치를 얻을 수 있는 조합을 빠르게 찾을 가능성이 높아집니다.

2) 가지치기 (Pruning)

최적 해를 찾을 수 없는 경로를 미리 제거하는 방법입니다. 예를 들어, 현재까지 선택된 물건들의 가치의 합과 남은 물건들의 최대 가치 가능성을 더해도 현재까지의 최적 해보다 작다면, 해당 경로는 탐색할 필요가 없습니다.

3) 비트마스킹 (Bitmasking)

물건의 개수가 비교적 적을 경우, 비트마스킹을 사용하여 상태를 표현하고 계산할 수 있습니다. 각 비트가 물건의 포함 여부를 나타내도록 하여, 메모리 사용량을 줄일 수 있습니다.

6. 주의사항 및 트러블슈팅

• 정확한 점화식: 점화식을 잘못 정의하면, 올바른 결과를 얻을 수 없습니다. 점화식을 세울 때는 각 상태의 의미와 이전 상태와의 관계를 명확하게 이해해야 합니다.
• 초기 조건: 초기 조건을 잘못 설정하면, DP 테이블의 값이 제대로 채워지지 않아 오답이 발생할 수 있습니다. 초기 조건은 문제의 상황에 맞게 신중하게 설정해야 합니다.
• 순회 방향: 1차원 배열을 사용할 때는 순회 방향 (앞에서부터 또는 뒤에서부터)이 매우 중요합니다. 순회 방향을 잘못 설정하면, 하나의 물건을 여러 번 담는 문제가 발생할 수 있습니다.
• 메모리 제한: 문제의 제약 조건에 따라, 공간 복잡도를 줄이는 최적화 기법을 사용해야 합니다.
• 시간 초과: O(nW) 시간 복잡도를 갖는 DP 솔루션이 시간 초과가 나는 경우, 최적화 기법을 적용하거나 다른 알고리즘을 고려해야 합니다.

7. 결론

0/1 배낭 문제는 DP를 이해하고, 문제 해결 능력을 향상시키는 데 매우 유용한 문제입니다. 기본적인 DP 해결법부터 공간 복잡도 최적화, 다양한 변형 문제, 그리고 최적화 기법까지 살펴보았습니다. 이 내용을 바탕으로 다양한 0/1 배낭 문제들을 해결하고, DP에 대한 이해를 더욱 깊게 할 수 있기를 바랍니다.