[AlgorithmSolving][DP] JUNGOL_1278: 배낭채우기2

1. 문제 내용

• 문제:

  정올 보석상에 도둑이 침입했다. 도둑은 배낭에 보석을 훔치려고 한다. 이때, 훔친 보석의 무게가 W를 넘어가면 배낭이 망가진다.

  각 보석의 값어치와 무게가 주어질 때, 도둑은 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되도록 보석을 배낭에 담으려고 한다. 이때 배낭에 담을 수 있는 최대 값어치를 구하시오.

• 입력:

  입력의 첫 줄은 보석의 개수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 

  둘째 줄부터 N+1줄에는 각 보석의 무게 W_i(1≤W_i≤W)와 값어치 P_i ( 1 <= P_i < 10,000)가 주어진다. 

  단, 보석은 각 종류별로 1개씩이다.

• 출력:

  출력은 보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되는 최대값을 출력한다.

2. 문제 유형 파악

이 문제는 DP 유형 중 하나인 “0/1 배낭 문제”로 “0/1 배낭 문제” 중에서 응용이 없는 가장 기초적인 문제라고 볼 수 있습니다.

3. 문제를 풀기 위한 핵심 아이디어

이 문제를 풀기 위한 핵심적인 아이디어는 다음과 같습니다.

1. DP 배열은 이전 항목의 결과에서 뺄지 넣을지를 정해야 하기 때문에 2차원으로 설정합니다.

2. 무게가 가장 낮은 물건으로 DP 배열의 초기화를 진행합니다. 물건은 하나 밖에 쓰지 못하므로 물건의 무게보다 무게값이 높은 부분에 물건의 가치값으로 채워줍니다.

3. 점화식 구성에는 이전 물건을 넣었을 때의 가치 값을 기준으로 점화식을 세워야 한다. 이전 물건의 현재 위치에서의 가치와 이전 물건에서의 현재 무게에서 물건의 무게를 뺀 곳의 가치에서 물건의 가치를 더한 것 중에서 더 큰 값을 현재 물건의 현재 무게에 넣어준다. 만약에 현재 무게가 물건의 무게보다 적을 경우에는 이전 물건의 현재 무게값을 그대로 넣어준다 이를 점화식으로 나타내면 다음과 같습니다.

\[DP[i][w] = \begin{cases} DP[i-1][w] & \text{if } w < W_i \\ \max(DP[i-1][w], DP[i-1][w - W_i] + P_i) & \text{if } w \ge W_i \end{cases}\]

4. 코드

이번 포스트에서 다루는 “0/1 배낭 문제”의 코드는 다음과 같습니다.

import sys

input = sys.stdin.readline

# 보석의 개수인 n과 전체 무게인 w를 받아옴
n, w = map(int, input().split())

# 입력으로 주어지는 보석들의 무게와 값어치를 받고 무게를 기준으로 정렬시켜줌
jewelry_list = []
for _ in range(n):
    weight, value = map(int, input().split())
    jewelry_list.append((weight, value))
jewelry_list = sorted(jewelry_list, key=lambda x:x[0])

# nx(w+1) 2차원 DP 배열을 선언하고 초기화 시켜줌
DP = [[0 for _ in range(w+1)] for _ in range(n)]
current_weight = jewelry_list[0][0]
current_value =jewelry_list[0][1]
for weight in range(1, w+1):
    if weight >= current_weight:
        DP[0][weight] = current_value

for i in range(1, n):
    
    #DP 배열의 값에 사용할 현재 보석의 무게와 값어치를 가져옴
    current_weight = jewelry_list[i][0]
    current_value =jewelry_list[i][1]
    
    # 무게가 0일 경우에는 값어치가 들어갈 수 없으므로 무게 1부터 w까지 반복을 진행
    for weight in range(1, w+1):
        
        # 만약 현재 무게가 현재 보석의 무게보다 크거나 같으면 보석이 들어갈 수도 있으므로 아래 점화식대로 DP 배열 업데이트
        if weight >= current_weight:
            DP[i][weight] = max(DP[i-1][weight], DP[i-1][weight-current_weight] + current_value)
        else: # 만약 현재 무게가 현재 보석의 무게보다 작다면 보석이 들어갈 수 없으므로 이전 보석으로 계산했던 값어치 값으로 업데이트
            DP[i][weight] = DP[i-1][weight]

# 최종 결과 출력
print(DP[n-1][w])

250

5. 복기 및 최적화

5.1 코드 복기

import sys

input = sys.stdin.readline

# 보석의 개수인 n과 전체 무게인 w를 받아옴
n, w = map(int, input().split())

# 입력으로 주어지는 보석들의 무게와 값어치를 받고 무게를 기준으로 정렬시켜줌
jewelry_list = []
for _ in range(n):
    weight, value = map(int, input().split())
    jewelry_list.append((weight, value))
jewelry_list = sorted(jewelry_list, key=lambda x:x[0])

# nx(w+1) 2차원 DP 배열을 선언하고 초기화 시켜줌
DP = [[0 for _ in range(w+1)] for _ in range(n)]
current_weight = jewelry_list[0][0]
current_value =jewelry_list[0][1]
for weight in range(1, w+1):
    if weight >= current_weight:
        DP[0][weight] = current_value

for i in range(1, n):
    
    #DP 배열의 값에 사용할 현재 보석의 무게와 값어치를 가져옴
    current_weight = jewelry_list[i][0]
    current_value =jewelry_list[i][1]
    
    # 무게가 0일 경우에는 값어치가 들어갈 수 없으므로 무게 1부터 w까지 반복을 진행
    for weight in range(1, w+1):
        
        # 만약 현재 무게가 현재 보석의 무게보다 크거나 같으면 보석이 들어갈 수도 있으므로 아래 점화식대로 DP 배열 업데이트
        if weight >= current_weight:
            DP[i][weight] = max(DP[i-1][weight], DP[i-1][weight-current_weight] + current_value)
        else: # 만약 현재 무게가 현재 보석의 무게보다 작다면 보석이 들어갈 수 없으므로 이전 보석으로 계산했던 값어치 값으로 업데이트
            DP[i][weight] = DP[i-1][weight]

# 최종 결과 출력
print(DP[n-1][w])

Gemini의 도움을 받아 위 코드의 복기를 진행해 보았습니다.

1. 정렬 불필요:

그리디 알고리즘과 달리, 0/1 배낭 DP에서는 보석의 순서가 결과에 영향을 미치지 않으므로 정렬을 진행할 필요가 없습니다.

1. 메모리 낭비:

2차원 배열 DP[i][w]를 보면 i번째 행을 계산할 때 오직 직전 행인 i-1 번째 행만 참조합니다. 즉 i-2, i-3 행의 데이터는 메모리만 차지할 뿐 다시 쓰이지 않습니다. N과 W가 매우 커진다면 메모리 초과(Memory Exceeded)가 날 수 있습니다.

5.2 코드 최적화

코드 복기 과정에서 나왔던 공간복잡도 최적화를 위해 1차원 배열만 사용하여 덮어쓰기 하는 방식으로 최적화 할 수 있습니다. 단 여기서 주의할 점은 배열을 덮어쓸 때 앞에서부터(정방향) 갱신하면 같은 보석을 여러 번 담는(무한 배낭) 버그가 발생합니다. 정방향으로 갱신하면 방금 갱신된 값을 뒤에서 또 참조하게 되어 같은 보석이 중복 계산되기 때문입니다. 따라서 뒤에서부터(역방향) 갱신하여 보석을 딱 한 번만 담도록 제어하는 것이 핵심입니다.

import sys
input = sys.stdin.readline

# 보석의 개수인 N과 배낭 용량 W 입력
N, W = map(int, input().split())

# 공간 복잡도 최적화: 1차원 DP 배열 선언 (크기 W+1)
dp = [0] * (W + 1)

for _ in range(N):
    weight, value = map(int, input().split())
    
    # [핵심 로직] 역방향 탐색 (W부터 weight까지)
    # 현재 보석의 무게보다 작은 경우는 어차피 담을 수 없으므로(기존 값 유지) 
    # weight까지만 탐색하여 불필요한 연산을 줄입니다.
    for j in range(W, weight - 1, -1):
        # 기존 최적값 vs 이 보석을 담기 위해 공간을 비웠을 때의 최적값 + 현재 가치
        dp[j] = max(dp[j], dp[j - weight] + value)

# 최종적으로 배낭의 최대 용량(W)일 때의 가치 출력
print(dp[W])

250