12865번 배낭문제: 동적 계획법으로 최대 가치 찾기

백준 12865번 '평범한 배낭(Knapsack)' 문제를 풀면서 동적 계획법(Dynamic Programming, DP)의 원리를 탐구했니다. 처음에는 복잡하게 느껴졌던 DP 테이블의 구조와 계산 방식이, 질문과 토론을 통해 점차 이해되었습니다.

학습 주제

• 공부 주제: 12865번 배낭문제 (평범한 배낭 문제)
• 학습 날짜: 2026년 2월 14일

질문과 탐구

처음 문제를 접했을 때, 모든 물건의 가능한 조합을 다 고려해야 하는 것이 아닌가 하는 막연한 생각이 들었습니다. 하지만 DP라는 접근 방식을 배우면서 "동적 계획법이란 무엇인가?", "DP 테이블은 어떻게 구성해야 하는가?", "반복문은 어떻게 짜야 하는가?", "시간 복잡도를 줄이기 위한 최적화 방법은 무엇인가?"와 같은 질문들이 자연스럽게 떠올랐습니다. 특히 2차원 DP 테이블에서 dp[i-1][w-weight[i]]와 같은 이전 상태를 참조하는 이유, 그리고 왜 그리디(Greedy) 방식으로는 최적해를 보장할 수 없는지에 대한 탐구해보았습니다.

핵심 학습 내용

DP 테이블 정의

dp[i][w]는 'i번째 물건까지 고려했을 때, 최대 용량이 w인 가방에서 얻을 수 있는 최대 가치'를 의미합니다. 여기서 i는 물건의 인덱스, w는 가방의 용량을 나타냅니다.

핵심 아이디어 및 선택의 기로

각 물건 i에 대해 두 가지 선택이 있습니다.

1. 물건 i를 넣지 않는 경우: 이 경우, i번째 물건을 고려하지 않았을 때의 최대 가치를 그대로 가져옵니다. 즉, dp[i-1][w] 값을 사용합니다.
2. 물건 i를 넣는 경우: 물건 i를 넣기 위해서는 해당 물건의 무게(weight[i])만큼의 용량이 필요합니다. 만약 현재 가방 용량 w가 물건 i의 무게보다 크거나 같다면, 물건 i를 넣을 수 있습니다. 이 경우, 물건 i를 넣기 전의 상태, 즉 i-1번째 물건까지 고려했을 때 w - weight[i] 용량으로 얻을 수 있는 최대 가치(dp[i-1][w-weight[i]])에 물건 i의 가치(value[i])를 더한 값이 됩니다.

이 두 경우 중 더 큰 가치를 가지는 쪽을 선택하여 dp[i][w]에 저장합니다.

# 물건 i의 무게: weight
# 물건 i의 가치: value
# 현재 가방 용량: w

# 물건 i를 넣을 수 있다면 (weight <= w)
dp[i][w] = max(
    dp[i-1][w],                  # 물건 i를 넣지 않는 경우 (이전 단계 그대로)
    dp[i-1][w - weight] + value  # 물건 i를 넣는 경우
)

# 물건 i를 넣을 수 없다면 (weight > w)
dp[i][w] = dp[i-1][w]            # 이전 단계 값 그대로 유지

테이블 구조와 계산 순서

2차원 DP 테이블은 (N+1) x (W+1) 크기로 생성되며, 첫 행(i=0)과 첫 열(w=0)은 초기값으로 0을 가집니다. 이는 물건이 없거나 용량이 0인 경우 최대 가치가 0이기 때문입니다.

계산 순서는 일반적으로 바깥쪽 반복문에서 물건 i를 1부터 N까지 순회하고, 안쪽 반복문에서 용량 w를 0부터 W까지 순회하며 각 셀의 값을 채워나갑니다.

# 초기화 (N+1) x (W+1) 크기의 dp 테이블을 0으로 채움
for i in range(N + 1):
    dp[i][0] = 0 # 용량이 0이면 가치 0
for w in range(W + 1):
    dp[0][w] = 0 # 물건이 0개면 가치 0

# DP 계산
for i in range(1, N + 1):           # 물건 1번부터 N번까지
    weight = items[i].first
    value = items[i].second
    for w in range(1, W + 1):       # 용량 1부터 W까지
        if weight <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight] + value)
        else:
            dp[i][w] = dp[i-1][w]

최종적으로 dp[N][W]에 문제의 해답, 즉 모든 물건을 고려했을 때 최대 용량 W에서 얻을 수 있는 최대 가치가 저장됩니다.

이해한 내용

DP는 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 최적해를 저장하여 전체 문제의 최적해를 효율적으로 구하는 기법임을 이해했습니다. 특히 배낭문제에서 dp[i][w]는 i번째 물건을 넣는지 안 넣는지에 대한 '선택'과, 그 선택에 따른 '상태 변화'(용량 감소)를 이전 단계의 최적값(dp[i-1][...])을 활용하여 계산한다는 점이 핵심이었습니다.

"가치값이 물건 조합을 대표하고, 이전 단계의 최적값은 다음 단계의 '그림자' 역할을 한다"는 비유를 통해 DP의 핵심 아이디어가 직관적으로 와닿았습니다. 가방의 높이(w)를 점점 올리면서, 각 높이에서 물건(i)을 넣을 수 있을 때 이전 조합(dp[i-1][w])과 현재 물건을 포함한 새로운 조합(dp[i-1][w-height[i]] + value[i]) 중 더 나은 것을 선택하는 과정이라고 생각하니 다른 관점에서 풀이방식을 이해할 수 있었습니다.

실전 적용

이 문제는 다양한 최적화 문제에 DP를 적용하는 기초가 됩니다.

• 실습 계획:

  • 1차원 DP로 공간 복잡도를 최적화하는 코드를 작성해 봅니다.
  • 다른 DP 문제(예: 편집 거리, 최장 공통 부분 수열)를 풀어보며 DP 개념을 확장합니다.
  • 현재 푼 12865번 문제를 다양한 예제 입력으로 테스트하여 이해도를 높입니다.

• 응용 아이디어:

  • 선택 알고리즘: 여러 아이템 중 제한된 예산(용량) 내에서 최대 만족도(가치)를 얻는 조합 찾기.
  • 자원 할당: 한정된 자원을 여러 작업에 배분하여 최대 효율을 내는 방안 탐색.
  • 경로 찾기: 특정 조건을 만족하는 최단/최장 경로 탐색 (DP 테이블의 구조를 그래프처럼 활용).

추가 학습 계획

• 1차원 DP 최적화: 2차원 DP 테이블을 1차원으로 줄이는 원리를 더 깊이 파고들어, 공간 복잡도를 O(W)로 줄이는 코드를 직접 구현해보고 이해합니다.
• 부분 배낭 문제 (Fractional Knapsack): 배낭문제와 비교하며, 물건을 쪼갤 수 있을 때 그리디 알고리즘으로 최적해를 구하는 방법을 학습합니다.
• 다양한 DP 문제: LeetCode, Programmers 등에서 DP 관련 문제들을 풀어보며 다양한 DP 패턴과 문제 해결 전략을 익힙니다.

참고 자료

• 백준 12865번 문제: https://www.acmicpc.net/problem/12865
• 동적 계획법(DP) 학습 자료: (AI와의 대화에서 직접 언급된 특정 문서나 링크는 없었으나, 학습 과정에서 얻은 개념들을 바탕으로 추후 관련 자료를 찾아볼 예정입니다.)