5-6. DP: 배낭 문제

1. 배낭 문제 소개

배낭 문제는 전형적인 조합 최적화 문제로, 주어진 제약 조건 하에서 가장 가치 있는 조합을 찾는 문제입니다. 이 문제는 현실 세계의 다양한 문제를 모델링하는 데 사용될 수 있으며, 컴퓨터 과학 분야에서 매우 중요한 알고리즘 문제입니다. 예를 들어, 여행을 갈 때 배낭에 넣을 수 있는 물건의 무게 제한이 있고, 각 물건마다 가치와 무게가 다를 때, 가장 가치 있는 물건들을 선택하는 문제를 배낭 문제로 표현할 수 있습니다.

1) 문제 정의

배낭 문제는 다음과 같이 정의됩니다.

• 입력:
  1. n개의 물건 (각 물건 i는 가치 v_i와 무게 w_i를 가짐)
  2. 배낭의 최대 허용 무게 W
• 출력: 배낭에 담을 물건들의 부분 집합 중, 총 무게가 W를 초과하지 않으면서, 총 가치가 최대가 되도록 하는 부분 집합.

2) 문제 유형

배낭 문제는 여러 변형이 존재하지만, 가장 기본적으로는 다음과 같은 두 가지 유형으로 나눌 수 있습니다.

• 0/1 배낭 문제 (0/1 Knapsack Problem): 각 물건을 배낭에 넣거나 넣지 않거나, 즉 0개 또는 1개만 넣을 수 있습니다.
• 분할 가능한 배낭 문제 (Fractional Knapsack Problem): 물건을 쪼개서 넣을 수 있습니다. 예를 들어, 금괴를 배낭에 넣을 때, 금괴의 일부분만 넣는 것이 가능합니다.

이 포스트에서는 0/1 배낭 문제에 초점을 맞춰 설명하겠습니다. 분할 가능한 배낭 문제는 그리디 알고리즘으로 효율적으로 해결할 수 있지만, 0/1 배낭 문제는 동적 프로그래밍(DP)을 사용해야 효과적으로 해결할 수 있습니다.

2. 0/1 배낭 문제의 DP 풀이

0/1 배낭 문제는 DP를 사용하여 효율적으로 해결할 수 있습니다. DP는 큰 문제를 작은 하위 문제로 나누어 해결하고, 하위 문제의 해결 결과를 저장하여 중복 계산을 피하는 방식입니다.

1) DP 테이블 정의

0/1 배낭 문제의 DP 테이블은 2차원 배열 dp[i][w]로 정의됩니다.

• dp[i][w]는 처음 i개의 물건을 고려하여, 최대 무게가 w인 배낭에 담을 수 있는 최대 가치를 나타냅니다.

2) 점화식 (Recurrence Relation)

DP의 핵심은 점화식을 정의하는 것입니다. 0/1 배낭 문제의 점화식은 다음과 같습니다.

$$ dp[i][w] = \begin{cases} 0, & \text{if } i = 0 \text{ or } w = 0 \\ dp[i-1][w], & \text{if } w_i > w \\ \max(dp[i-1][w], dp[i-1][w - w_i] + v_i), & \text{otherwise} \end{cases} $$

• i <mark class="highlight"><strong><u> 0 또는 w </u></strong></mark> 0인 경우: 물건이 없거나, 배낭의 허용 무게가 0인 경우, 담을 수 있는 가치는 0입니다.
• w_i > w인 경우: 현재 물건 i의 무게가 배낭의 허용 무게 w보다 큰 경우, 현재 물건을 담을 수 없으므로 이전 단계의 최대 가치를 그대로 가져옵니다.

• otherwise: 현재 물건 i를 담을 수 있는 경우, 두 가지 선택 중 더 큰 가치를 선택합니다.

  • dp[i-1][w]: 현재 물건을 담지 않는 경우 (이전 단계의 최대 가치)
  • dp[i-1][w - w_i] + v_i: 현재 물건을 담는 경우, 배낭의 허용 무게에서 현재 물건의 무게를 뺀 상태에서 이전 물건들로 얻을 수 있는 최대 가치에 현재 물건의 가치를 더함.

3) 초기 조건

DP 테이블을 채우기 위한 초기 조건은 다음과 같습니다.

• dp[0][w] = 0 (모든 w에 대해): 물건이 없는 경우, 배낭의 허용 무게와 상관없이 최대 가치는 0입니다.
• dp[i][0] = 0 (모든 i에 대해): 배낭의 허용 무게가 0인 경우, 담을 수 있는 물건이 없으므로 최대 가치는 0입니다.

4) DP 테이블 채우기

점화식과 초기 조건을 바탕으로 DP 테이블을 채워나갑니다.

• i를 1부터 n까지 반복합니다 (물건의 개수).
• w를 1부터 W까지 반복합니다 (배낭의 허용 무게).
• 점화식을 사용하여 dp[i][w] 값을 계산합니다.

5) 코드 예시 (Python)

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# 예시 사용
weights = [2, 3, 4, 5]
values = [1, 2, 3, 4]
capacity = 5
max_value = knapsack_01(weights, values, capacity)
print(f"최대 가치: {max_value}")

3. 최적 부분 구조 (Optimal Substructure)

배낭 문제는 최적 부분 구조를 가집니다. 즉, 문제의 최적 해는 부분 문제의 최적 해로부터 구성될 수 있습니다. 0/1 배낭 문제의 경우, 다음과 같은 최적 부분 구조를 가집니다.

• 만약 물건 i를 배낭에 넣지 않는다면, 최대 가치는 물건 1부터 i-1까지의 물건들로 배낭의 무게 제한 w 내에서 얻을 수 있는 최대 가치와 같습니다.
• 만약 물건 i를 배낭에 넣는다면, 최대 가치는 물건 1부터 i-1까지의 물건들로 배낭의 무게 제한 w - w_i 내에서 얻을 수 있는 최대 가치에 물건 i의 가치를 더한 것과 같습니다.

이러한 최적 부분 구조는 DP를 적용할 수 있는 중요한 조건입니다. 문제를 작은 하위 문제로 나누어 해결하고, 하위 문제의 최적 해를 결합하여 전체 문제의 최적 해를 구할 수 있기 때문입니다.

4. 메모이제이션과 탭ulated 방식 비교

DP는 일반적으로 두 가지 방식으로 구현됩니다.

1) 메모이제이션 (Top-down)

메모이제이션은 재귀 함수를 사용하여 DP를 구현하는 방식입니다. 재귀 호출을 통해 문제를 작은 하위 문제로 나누어 해결하고, 각 하위 문제의 결과를 저장 (메모이제이션)하여 중복 계산을 피합니다.

• 장점:

  • 직관적이고 코드가 간결합니다.
  • 필요한 하위 문제만 계산하므로, 모든 하위 문제를 계산하는 탭ulated 방식보다 효율적일 수 있습니다 (단, 모든 하위 문제를 계산해야 하는 경우에는 탭ulated 방식이 더 효율적임).
  • 단점:
  • 재귀 호출로 인한 오버헤드가 발생할 수 있습니다 (함수 호출, 스택 메모리).
  • 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다.

2) 탭ulated 방식 (Bottom-up)

탭ulated 방식은 반복문을 사용하여 DP 테이블을 채워나가는 방식입니다. 작은 하위 문제부터 해결하고, 그 결과를 바탕으로 더 큰 하위 문제를 해결해 나갑니다.

• 장점:

  • 재귀 호출 오버헤드가 없어 메모이제이션 방식보다 빠릅니다.
  • 스택 오버플로우 발생 위험이 없습니다.
  • 단점:
  • 문제를 분해하는 과정이 직관적이지 않을 수 있습니다.
  • 모든 하위 문제를 계산해야 하므로, 메모이제이션 방식보다 비효율적일 수 있습니다 (단, 모든 하위 문제를 계산해야 하는 경우에는 탭ulated 방식이 더 효율적임).

0/1 배낭 문제의 경우, 탭ulated 방식이 일반적으로 더 효율적입니다. 하지만 문제의 특성에 따라 메모이제이션 방식이 더 적합할 수도 있습니다.

5. 시간 복잡도 분석

0/1 배낭 문제의 DP 풀이의 시간 복잡도는 $O(nW)$입니다. 여기서 n은 물건의 개수이고, W는 배낭의 최대 허용 무게입니다. DP 테이블을 채우기 위해 n개의 물건에 대해 W개의 무게를 모두 확인해야 하기 때문입니다.

공간 복잡도는 $O(nW)$입니다. n x W 크기의 DP 테이블을 사용하기 때문입니다. 공간 복잡도를 최적화하기 위해, 이전 행의 정보만 저장하는 방식으로 공간을 줄일 수 있습니다 (예: 1차원 배열 사용).

6. 응용 및 활용 사례

0/1 배낭 문제는 다양한 분야에서 활용될 수 있습니다.

• 자원 할당 문제: 제한된 자원 (예: 예산, 시간)을 가지고 가장 높은 효용을 얻기 위해, 어떤 프로젝트나 활동에 자원을 할당할지 결정하는 문제.
• 포트폴리오 최적화: 주어진 예산 내에서 다양한 자산 (주식, 채권 등)을 선택하여 투자 포트폴리오를 구성하고, 가장 높은 수익을 얻는 조합을 찾는 문제.
• 물류 및 창고 관리: 창고에 보관할 상품을 선택하거나, 트럭에 적재할 화물을 선택하여 수송 효율을 극대화하는 문제.
• 게임 개발: 게임 내 아이템의 가치와 무게를 고려하여, 캐릭터가 소지할 수 있는 아이템의 최대 가치를 결정하는 문제.

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

• 메모리 제한: n과 W의 값이 매우 큰 경우, DP 테이블의 크기가 커져 메모리 제한에 걸릴 수 있습니다. 이 경우, 공간 복잡도를 줄이기 위한 최적화 기법 (예: 1차원 배열 사용)을 고려해야 합니다.
• 정수 오버플로우: 가치 (v_i)의 값이 큰 경우, 계산 과정에서 정수 오버플로우가 발생할 수 있습니다. long long과 같은 더 큰 자료형을 사용하거나, 가치를 적절하게 스케일링하여 오버플로우를 방지해야 합니다.
• 입력 데이터 검증: 입력 데이터 (무게, 가치, 배낭의 허용 무게)가 유효한 범위 내에 있는지 확인해야 합니다. 음수 값은 처리할 수 없으므로, 음수 값이 입력될 경우 예외 처리를 해야 합니다.
• 최적 해 복원: DP 테이블을 채운 후, 어떤 물건들이 선택되었는지 (최적 해)를 역추적해야 할 수 있습니다. 이를 위해서는 DP 테이블을 채우는 과정에서 각 셀의 값을 계산할 때, 어떤 물건을 선택했는지에 대한 정보를 별도로 저장해야 합니다.

8. 결론

배낭 문제는 동적 프로그래밍을 효과적으로 적용할 수 있는 대표적인 문제 중 하나입니다. 0/1 배낭 문제의 DP 풀이를 이해하고, 점화식, 초기 조건, DP 테이블 채우는 과정을 숙지하면, 다양한 변형 문제에 적용할 수 있습니다. 최적 부분 구조와 메모이제이션/탭ulated 방식에 대한 이해는 문제 해결 능력 향상에 도움이 될 것입니다.