DP 기초
ds-10(동적 프로그래밍 기초)에서는 피보나치 하나로 완전탐색·메모이제이션·타뷸레이션을 비교했다면, 여기서는 0/1 배낭 문제(Knapsack)로 DP를 한 단계 확장합니다. 피보나치는 1차원 표였지만, 배낭 문제는 "아이템 개수"와 "배낭 용량"이라는 두 축을 가진 2차원 표를 채워야 합니다.
핵심 개념
0/1 배낭 문제란
무게와 가치가 정해진 아이템들이 있을 때, 정해진 무게 한도(배낭 용량) 안에서 가치의 합이 최대가 되도록 아이템을 고르는 문제입니다. 각 아이템은 "넣거나(1) 안 넣거나(0)"만 가능합니다.
핵심 개념
2차원 DP 테이블
dp[i][w]는 "처음 i개의 아이템만 고려했을 때, 용량 w로 얻을 수 있는 최대 가치"를 의미합니다. 행은 아이템 개수, 열은 용량을 나타냅니다.
핵심 개념
점화식: 포함 vs 제외
매 칸마다 "이 아이템을 포함했을 때"와 "포함하지 않았을 때" 중 더 큰 값을 선택합니다: dp[i][w] = max(dp[i-1][w], dp[i-1][w-무게]+가치) (w가 아이템 무게 이상일 때만 포함 경우를 따집니다).
핵심 개념
기저 사례
아이템이 0개(0행)이거나 용량이 0(0열)이면 담을 수 있는 가치도 항상 0입니다. 이 두 경계가 모든 계산의 출발점입니다.
핵심 개념
값만으론 부족하다 — 역추적
테이블의 오른쪽 아래 칸은 "최댓값"만 알려줄 뿐, "어떤 아이템을 골랐는지"는 알려주지 않습니다. 어떤 아이템이 선택됐는지 알려면 표를 거슬러 올라가는 역추적이 필요합니다.
핵심 개념
시간·공간 복잡도
아이템 수 n, 용량 W일 때 표의 칸 수는 n×W개이고 각 칸은 O(1)에 계산되므로 시간복잡도는 O(nW)입니다. 표 전체를 저장하므로 공간복잡도도 O(nW)입니다.
동적 계획법과 배낭 문제
동적 계획법(Dynamic Programming)은 큰 문제를 겹치는 작은 문제로 나누고, 작은 문제의 답을 저장해 다시 계산하지 않는 방법입니다. 1950년대에 리처드 벨만(Richard Bellman)이 정립하고 이름을 붙인 것으로 알려져 있고, 대표 저서는 『Dynamic Programming』(Princeton University Press, 1957)입니다. 0/1 배낭 문제는 이 방법을 표로 보여 주는 대표적인 예입니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
DP 문제인지 어떻게 알아보나요?
큰 문제의 답이 작은 문제의 답으로 만들어지고(최적 부분 구조), 같은 작은 문제가 여러 번 나오는지(겹치는 부분 문제)를 봅니다. 둘 다 있으면 저장해 재사용하는 DP가 효과적입니다.
면접 질문
0/1 배낭의 공간을 줄일 수 있나요?
최댓값만 필요하면 바로 윗줄만 있으면 되므로 한두 줄만 남겨 O(W) 공간으로 줄일 수 있습니다. 대신 어떤 아이템을 골랐는지 역추적하려면 표 전체가 필요합니다.
면접 질문
메모이제이션과 표 채우기(타뷸레이션)는 어떻게 다른가요?
메모이제이션은 재귀로 위에서 내려가며 필요한 부분 문제만 계산해 저장하고, 표 채우기는 작은 문제부터 순서대로 모두 계산합니다. 같은 점화식을 쓰지만 호출 깊이와 불필요한 계산이 달라집니다.
면접 질문
거스름돈 문제를 DP로 풀면 왜 그리디보다 확실한가요?
그리디는 매 순간 가장 큰 동전만 보지만 DP는 모든 금액의 최소 개수를 아래에서부터 쌓아 올려서, 동전 단위가 애매해도 최적을 보장합니다.
실제 시스템에서는
functools — functools.cache는 같은 인자로 다시 호출하면 저장된 결과를 돌려줍니다(인자는 해시 가능해야 합니다). lru_cache는 기본 maxsize가 128이라 오래 쓰지 않은 결과는 버려져 다시 계산될 수 있습니다. 메모이제이션을 직접 구현하지 않고 쓸 수 있습니다.
함께 보면 좋은 토픽
참고 자료
Java — 0/1 배낭 문제 (2차원 DP 테이블)
/* ── dp[i][w]: 처음 i개 아이템, 용량 w일 때의 최대 가치 ──── */ public int knapsack(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; // 0행·0열은 자동으로 0(기저 사례) for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { int without = dp[i - 1][w]; // 이 아이템을 제외했을 때 int with = (weights[i - 1] <= w) ? dp[i - 1][w - weights[i - 1]] + values[i - 1] // 포함했을 때 : -1; // 무게 초과 — 포함 불가 dp[i][w] = Math.max(without, with); } } return dp[n][capacity]; }
without은 바로 위 칸(dp[i-1][w])을, with는 대각선 위 칸(dp[i-1][w-무게])을 참조합니다 — 두 칸 모두 "이미 계산된 이전 줄"이라 순서대로 채우면 항상 값이 준비되어 있습니다.
무게가 용량을 넘으면 애초에 넣을 수 없으므로 with를 계산 자체를 하지 않고(-1로 처리) without만 남습니다.
Java — 선택 아이템 역추적
/* ── 완성된 표를 오른쪽 아래에서 왼쪽 위로 거슬러 올라감 ───── */ public List<Integer> findSelectedItems(int[][] dp, int[] weights, int n, int capacity) { List<Integer> selected = new ArrayList<>(); int w = capacity; for (int i = n; i >= 1; i--) { if (dp[i][w] != dp[i - 1][w]) { // 값이 다르면 이 아이템 덕분에 달라진 것 selected.add(0, i - 1); // 아이템 (i-1)을 포함했다고 기록 w -= weights[i - 1]; // 그만큼 용량을 되돌려 계속 거슬러 올라감 } // 값이 같으면 이 아이템은 포함되지 않은 것 — w는 그대로 두고 한 줄 위로 } return selected; }
dp[i][w] != dp[i-1][w]가 핵심입니다 — 아이템 i를 고려하기 전(i-1)과 후(i)의 값이 달라졌다면, 그 차이는 아이템 i를 포함했기 때문입니다.
포함으로 판단되면 용량 w에서 그 아이템의 무게만큼을 빼고 한 줄 위로 이동합니다 — "이 아이템을 빼면 얼마가 남았어야 하는지"를 거슬러 올라가는 것입니다.
Java — 공간 최적화 (1차원 배열, O(W) 공간)
/* ── 매 행이 바로 이전 행만 참조하므로 배열 1개로 축소 가능 ── */ public int knapsackOptimized(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.length; i++) { for (int w = capacity; w >= weights[i]; w--) { // 반드시 오른쪽에서 왼쪽으로! dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); } } return dp[capacity]; }
2차원 표의 각 행은 바로 위 행만 참조하므로, 배열 하나를 재사용하면 공간을 O(nW)에서 O(W)로 줄일 수 있습니다 — ds-10(동적 프로그래밍 기초)에서 피보나치를 변수 2개로 줄인 것과 같은 최적화 원리입니다.
단, 용량을 큰 값에서 작은 값 순서로 갱신해야 합니다.
왼쪽에서 오른쪽으로 갱신하면 같은 아이템을 여러 번 포함하는 것과 같은 효과가 생겨(0/1이 아니라 무제한이 되어) 답이 달라집니다.
이 시각화의 역추적 기능은 2차원 표가 있어야 가능해, 코드 탭에서는 참고용으로만 소개합니다.
Q1
0/1 배낭 문제에서 '0/1'이 의미하는 것은?
Q2
배낭 문제의 DP 테이블에서 행과 열은 보통 무엇을 나타내나요?
Q3
DP 테이블을 채운 뒤 역추적(backtracking)으로 하는 일은?