0/1 배낭과 공간 최적화
0/1 배낭 점화식을 도출하고 2차원 표를 채운 다음, 용량을 역순으로 순회해 1차원 배열로 줄입니다.
0/1 배낭과 공간 최적화은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
0/1 배낭 문제
0/1 배낭 문제는 다음과 같습니다. 각 항목에 무게 w[i]와 가치 v[i]가 주어지고, 용량이 W인 배낭이 있을 때 용량을 초과하지 않으면서 총 가치를 최대화하도록 항목을 선택합니다. 각 항목은 정확히 한 번만 선택합니다(0 = 건너뜀, 1 = 선택). 이는 동일한 합의 부분 집합 분할과 목표 합을 비롯한 다양한 면접 DP 문제의 대표적인 유형입니다.
DP 상태와 점화식
dp[i][c]를 처음 i개 항목을 사용하고 용량이 c일 때의 최대 가치로 정의합니다. 항목 i에 대해서는 두 가지 선택이 있습니다. 건너뛰기(dp[i-1][c]) 또는 w[i] <= c일 때 선택하기(dp[i-1][c-w[i]] + v[i])입니다. w[i] <= c일 때 점화식은 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])이고, 그렇지 않으면 dp[i][c] = dp[i-1][c]입니다. 기저 사례는 모든 c에 대해 dp[0][c] = 0입니다.
2차원 DP 표 구현
2차원 표에는 (n+1) x (W+1)개의 항목이 있으며, 각 항목에 대해 행을 하나씩 채웁니다. 모든 행을 채우고 나면 dp[n][W]에 최대 가치가 저장됩니다. 시간 복잡도는 O(n × W)이고 공간 복잡도는 O(n × W)입니다. 이는 유사 다항식 복잡도이지만 W가 작을 때는 효율적입니다.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 101차원 DP에서 용량을 역순으로 순회하는 이유
핵심 관찰은 행 i가 행 i-1에만 의존한다는 점입니다. 따라서 하나의 1차원 배열을 사용해 제자리에서 갱신할 수 있습니다. 하지만 용량 c를 왼쪽에서 오른쪽으로(작은 값에서 큰 값으로) 순회하면 항목 i가 두 번 계산될 수 있습니다. 이미 항목 i를 포함하는 c-w[i]의 갱신된 값을 다시 사용할 수 있기 때문입니다. 오른쪽에서 왼쪽으로(큰 값에서 작은 값으로) 순회하면 각 항목이 한 번의 행 갱신에서 최대 한 번만 사용됩니다.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous row1차원 공간 최적화 구현
배열 하나만 유지하고 용량을 W에서 w[i]까지 내림차순으로 순회하면 O(W) 공간으로 2차원 표와 같은 결과를 얻을 수 있습니다. 시간 복잡도는 여전히 O(n × W)입니다. 이 공간 최적화는 반드시 기억해야 합니다. 면접관은 2차원 배낭 DP를 1차원으로 줄이라고 자주 요구합니다.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10selected 항목 복원
어떤 항목이 selected인지 알아내려면 전체 2차원 표가 필요합니다. 표를 모두 채운 뒤 dp[n][W]에서 시작해 역으로 추적합니다. dp[i][c] != dp[i-1][c]이면 항목 i가 포함된 것이므로 해당 항목의 무게를 c에서 빼고 행 i-1로 이동합니다. i = 0이 될 때까지 계속합니다. 1차원 최적화를 사용하면 이 복원 기능을 잃게 됩니다.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))실전 예시: 총 가치 최대화
다음 항목을 생각해 보겠습니다. weights=[2,3,4,5], values=[3,4,5,6], W=8입니다. 최적의 선택은 무게 3(가치 4)인 항목과 무게 5(가치 6)인 항목을 선택하는 것입니다. 총 무게는 8이고 가치는 10입니다. 또는 무게 2와 5를 선택하면 총 가치는 9이고, 무게 2와 3을 선택하면 가치는 7입니다. DP는 정확히 최대값 10을 찾습니다. 탐욕적 접근법을 사용해 가치 대 무게 비율이 가장 높은 항목을 선택하면 비율이 1.5인 항목(무게 2, 가치 3)을 먼저 선택하게 되지만, 이것이 항상 최적인 것은 아닙니다.
분할 배낭과 0/1 배낭 비교
분할 배낭에서는 항목을 일부만 선택할 수 있습니다. 가치/무게 비율을 기준으로 정렬하면 탐욕적으로 해결할 수 있습니다. 0/1 배낭에서는 항목을 나눌 수 없으므로 탐욕적 방법이 실패하고 DP가 필요합니다. 면접관은 이 차이를 통해 탐욕적 방법을 언제 적용할 수 있는지 알고 있는지 확인합니다. 분할 변형에 대한 질문을 받으면 즉시 정렬을 사용하는 탐욕적 방법을 언급하고, 0/1 문제라면 DP를 사용해야 합니다.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))유사 다항식 시간 복잡도
0/1 배낭은 NP-완전 문제이지만 O(nW) 시간에 해결할 수 있습니다. 이 모순은 O(nW)가 유사 다항식이기 때문에 생깁니다. W는 입력 크기가 아니라 값입니다. W의 이진 표현에는 O(log W)비트가 필요하므로 실제 복잡도는 O(n × 2^(log W))이고 입력 크기에 대해 지수적입니다. W가 작을 때(예: 10⁴)는 DP가 실용적이지만, W가 10⁹까지 커질 수 있다면 다른 접근법이 필요합니다.
면접관의 추가 질문: 큰 용량
면접관이 W를 매우 크게(예: 10⁹) 제한하지만 n은 작게 주면 표준 DP는 사용할 수 없습니다. 대안으로는 (1) O(2^(n/2) × n) 시간의 중간에서 만나기, (2) 분할 변형을 위한 탐욕적 근사, (3) 분기 한정법이 있습니다. 대부분의 면접 문제에서 W <= 10⁵라면 역순 순회를 사용하는 1차원 DP가 기대되는 답입니다.
큰 용량을 위한 중간에서 만나기
W가 매우 크지만 n은 작은 경우(예: n=40), 표준 O(nW) DP는 실행하기 어렵고 완전 탐색 O(2^n)은 너무 느립니다. 중간에서 만나기는 항목을 두 절반으로 나누고 각 절반에서 가능한 모든 2^(n/2)개 부분 집합을 열거한 뒤 최적으로 짝을 맞춥니다. 한쪽 절반을 무게순으로 정렬한 다음 다른 절반의 각 부분 집합에 대해 이진 탐색으로 용량 안에서 가장 좋은 짝을 찾습니다. 시간 복잡도는 O(2^(n/2) × n)이며 n이 40까지일 때 실용적입니다.
빠른 확인
이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비의 개념을 얼마나 이해했는지 확인해 보세요.
수업 복습
이 수업에서 배운 내용은 다음과 같습니다. 0/1 배낭 DP에서 상태 dp[i][c]는 i개 항목과 용량 c가 주어졌을 때의 최대 가치를 나타냅니다, 점화식은 각 항목을 건너뛰거나 선택합니다, 그리고 1차원 공간 최적화에서는 항목의 중복 계산을 막기 위해 용량을 오른쪽에서 왼쪽으로 순회합니다. 다음에는 항목을 재사용할 수 있는 무제한 배낭을 살펴보고 이를 동전 교환 II에 적용합니다.
자주 묻는 질문
“0/1 배낭과 공간 최적화” 강의는 무료인가요?
네 — “0/1 배낭과 공간 최적화” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“0/1 배낭과 공간 최적화”에서 뭘 배우나요?
0/1 배낭 점화식을 도출하고 2차원 표를 채운 다음, 용량을 역순으로 순회해 1차원 배열로 줄입니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“0/1 배낭과 공간 최적화” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 0/1 배낭과 공간 최적화
- 무한 배낭과 동전 교환 II
- 동일한 부분집합 합으로 분할
- 양수와 음수 부호를 사용한 목표 합