| 작성자 | 이재영 |
| 일 시 | 2024. 11. 12 (화) 18:00 ~ 21:00 |
| 장 소 | 복지관 B-128-1호 |
| 참가자 명단 | 임혜진, 장원준, 이재영, 성창민, 김명원 |
| 사 진 |  |
이번 모각코에서 는 백준 골드 수준의 DP 문제를 풀어보았다. 앞으로 어려운 문제를 대비하며 기초를 탄탄히 다지는 중이다. 다음은 이번에 풀어본 문제와 그 풀이 과정을 정리한 내용이다.
1. 백준 12865번 - 평범한 배낭 (0/1 Knapsack 문제)
문제
물건 N개가 있고, 각 물건은 무게 W와 가치 V를 가지고 있습니다. 배낭에는 최대 K의 무게까지 담을 수 있으며, 우리는 배낭에 담을 수 있는 물건들의 가치 합이 최대가 되도록 선택하고자 합니다.
즉, 물건을 적절히 선택하여 배낭에 담았을 때 얻을 수 있는 최대 가치를 구하는 문제입니다.
입력
첫 줄에 물건의 수 N과 배낭의 최대 무게 K가 주어집니다.
이후 N줄에는 각 물건의 무게 W와 가치 V가 주어집니다.
출력
배낭에 담을 수 있는 물건들의 가치 합의 최댓값을 출력합니다.
문제 분석 및 부분 문제 정의
이 문제는 0/1 배낭 문제로, 물건을 선택할 때 각 물건을 넣거나 넣지 않는 두 가지 선택지가 존재한다.
문제를 작은 부분 문제로 나누어 보면, i번째 물건까지 고려했을 때의 최대 가치를 찾는 것으로 나눌 수 있다.
점화식 도출
각 물건 i와 현재 배낭 무게 j를 기준으로 점화식을 도출할 수 있다.
- 물건 i를 배낭에 담지 않는 경우: dp[i][j] = dp[i-1][j]
- 물건 i를 배낭에 담는 경우 (단, j >= W일 때): dp[i][j] = dp[i-1][j-W] + V
즉, 각 경우를 비교하여 더 큰 값을 택하게 되면 최적해를 구할 수 있다.
초기 조건 설정
dp[i][j]는 i번째 물건까지 고려하고 j만큼의 무게를 허용할 때 얻을 수 있는 최대 가치이다.
초기에는 물건을 담지 않는 상태로 시작하기 때문에, 초기 상태로 dp[0][j] = 0으로 설정한다.
import sys
input = sys.stdin.readline
# N: 물건의 개수, K: 배낭의 최대 무게
N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
# dp 배열 초기화 (각 weight에 대해 최대 가치 저장)
dp = [0] * (K + 1)
for weight, value in items:
for w in range(K, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
print(dp[K])
- DP 배열 초기화: 최대 무게 K에 대해 각 무게별 최대 가치를 저장할 DP 배열을 초기화했다.
- 역방향 반복: 무게별로 값을 갱신할 때, 역방향으로 갱신하여 현재 물건을 중복해서 담는 경우를 방지했다.
- 최댓값 갱신: 각 무게에 대해 물건을 담는 경우와 담지 않는 경우의 가치를 비교해 최댓값을 갱신했다.
이 문제를 통해 0/1 배낭 문제의 DP 해결 방법을 복습할 수 있었다.
배낭 문제는 다양한 유형의 DP 문제에서 등장하기 때문에 반복적으로 풀어보는 것이 큰 도움이 되는 것 같다.