무한 배낭과 동전 교환 II
용량을 정순으로 순회해 항목을 재사용할 수 있도록 하고, 이 변형으로 coin-change-II(방법 수 세기)와 막대 자르기 문제를 해결합니다.
무한 배낭과 동전 교환 II은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
무제한 배낭 개념
무제한 배낭에서는 각 항목을 횟수 제한 없이 선택할 수 있습니다(각 항목을 최대 한 번만 사용하는 0/1 배낭과 다릅니다). 상태 정의는 같습니다. dp[c]는 용량 c로 얻을 수 있는 최대 가치입니다. 하지만 순회 방향이 달라집니다. 항목을 재사용할 수 있으므로 dp[c]를 갱신할 때 현재 항목을 다시 사용할 수 있어야 하며, 따라서 용량을 왼쪽에서 오른쪽으로(정방향으로) 순회합니다.
정방향 순회로 재사용 허용
0/1 배낭에서는 재사용을 막기 위해 오른쪽에서 왼쪽으로 순회했습니다. 무제한 배낭에서는 반대로 왼쪽에서 오른쪽으로 순회합니다. dp[c]를 계산할 때 dp[c-w]는 현재 순회에서 이미 갱신된 상태일 수 있습니다. 즉, 항목 i가 이미 포함되어 있을 수 있습니다. 이것이 바로 원하는 동작입니다. 항목 i가 이미 포함된 해에 항목 i를 다시 추가할 수 있기 때문입니다.
def unbounded_knapsack(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): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9동전 교환 II: 방법의 수 세기
동전 교환 II는 동전 단위와 금액이 주어졌을 때 해당 금액을 만드는 서로 다른 방법의 수를 구하는 문제입니다(각 동전은 제한 없이 사용할 수 있습니다). 이는 가치를 최대화하는 대신 combinations를 세는 무제한 배낭 변형입니다. dp[c]를 금액 c를 만드는 방법의 수로 정의합니다. 기저 사례는 dp[0] = 1입니다(0을 만드는 한 가지 방법은 아무것도 선택하지 않는 것입니다).
동전 교환 II 구현
각 동전에 대해 금액을 왼쪽에서 오른쪽으로 순회하며 누적합니다. dp[c] += dp[c - coin]. 기저 사례인 dp[0] = 1이 개수 계산의 시작값이 됩니다. 바깥쪽 반복문은 동전을 순회하고 안쪽 반복문은 금액을 순회한다는 점에 유의하세요. 각 동전 단위를 바깥쪽 순회에서 정확히 한 번만 처리하므로 자연스럽게 조합의 개수를 구합니다(permutations가 아님).
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1조합과 순열 비교
반복문의 순서가 매우 중요합니다. 금액을 바깥쪽 반복문에서 순회하고 동전을 안쪽 반복문에서 순회하면 permutations(순열)을 셉니다(순서가 중요합니다). 금액이 5이고 동전이 [1,2]일 때 1+2+2와 2+1+2를 별도로 계산합니다. 동전을 바깥쪽 반복문에서 순회하면 combinations(조합)을 셉니다(순서는 중요하지 않습니다). 1+2+2와 2+1+2를 같은 것으로 봅니다. 동전 교환 II는 combinations를 요구하므로 동전이 바깥쪽 반복문에 와야 합니다.
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13막대 자르기 문제
또 다른 고전적인 무제한 배낭 문제입니다. 길이 n인 막대와 길이 1부터 n까지의 각 막대 길이에 대한 가격이 주어졌을 때, 막대를 최적으로 잘라 얻을 수 있는 최대 수익을 구합니다. 길이 l인 각 조각은 price[l]에 팔 수 있으며, 조각은 재사용할 수 있습니다(막대를 같은 길이의 여러 조각으로 자를 수 있습니다). 이는 W = n이고 항목이 서로 다른 절단 길이인 무제한 배낭으로 바로 대응됩니다.
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22동전 교환 I: 최소 동전 수
동전 교환 I(서로 다른 문제)는 목표 금액을 만들기 위해 필요한 최소 동전 수를 구하는 문제입니다. 여기서 dp[c]는 금액 c를 만드는 데 필요한 최소 동전 수입니다. 점화식은 dp[c] = min(dp[c], dp[c - coin] + 1)입니다. dp[0] = 0을 제외한 모든 항목을 inf로 초기화합니다. 이 문제도 무제한 문제이므로(동전을 재사용할 수 있으므로) 왼쪽에서 오른쪽으로 순회합니다. 유한한 값이면 dp[amount]를 반환하고, 그렇지 않으면 -1을 반환합니다.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1핵심 차이: 최대화, 최소화, 개수 세기
세 가지 무제한 배낭 변형은 dp[c-coin]에 서로 다른 연산을 적용합니다. 가치 최대화: dp[c] = max(dp[c], dp[c-w] + v)이며 0으로 초기화합니다. 비용 최소화: dp[c] = min(dp[c], dp[c-coin] + 1)이며 inf로 초기화하고 dp[0]=0으로 설정합니다. 방법의 수 세기: dp[c] += dp[c-coin]이며 0으로 초기화하고 dp[0]=1로 설정합니다. 면접 문제에서 어떤 변형이 적용되는지 알아내는 것이 문제 해결의 절반입니다.
복잡도와 면접 팁
모든 무제한 배낭 변형은 항목 유형 수가 n이고 목표 금액이 W일 때 O(n × W) 시간과 O(W) 공간에 실행됩니다. 동전 문제에서는 n이 동전 단위의 개수입니다. 면접에서는 변형(최대화/최소화/개수)을 명시하고 1차원 DP를 작성하며, 바깥쪽 반복문이 동전인지 금액인지 분명히 설명하세요. 면접관은 이 구분을 통해 DP를 깊이 이해하고 있는지 확인합니다.
무제한 배낭과 0/1 배낭 구분
다음 단서를 사용해 어떤 변형이 적용되는지 구분하세요. 무제한 재사용 → 무제한 배낭(정방향 순회), 각 항목을 정확히 한 번 → 0/1 배낭(역방향 순회), 문제에서 ‘횟수 제한 없이’, ‘무한히 공급됨’ 또는 ‘재사용 가능’이라고 함 → 무제한 배낭입니다. 예를 들어 동전 교환, 막대 자르기, 정수 분할은 모두 무제한 배낭입니다. 부분 집합 합, 분할, 0/1 배낭은 0/1 문제입니다. 이를 잘못 구분하면 원인을 찾기 어려운 오답이 발생합니다.
정수 분할과 기타 변형
정수 분할(LeetCode 343)은 정수 n을 2개 이상의 양의 정수로 나누어 곱을 최대화하는 문제입니다. 이는 ‘항목’이 2부터 n-1까지의 정수인 무제한 배낭 문제입니다. dp[i]를 합이 i가 되는 정수들의 곱 중 최댓값으로 정의합니다. 2부터 i까지의 각 항목 j에 대해 dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))를 적용합니다. 이 예시는 무제한 패턴이 동전 문제를 넘어 어떻게 일반화되는지 보여 줍니다.
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)빠른 확인
이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비의 개념을 얼마나 이해했는지 확인해 보세요.
수업 복습
이 수업에서 배운 내용은 다음과 같습니다. 무제한 배낭은 항목 재사용을 허용하기 위해 용량을 왼쪽에서 오른쪽으로 순회합니다, 동전 교환 II는 동전을 바깥쪽 반복문에 배치해 combinations를 셉니다, 그리고 세 가지 변형인 최대화, 최소화, 개수 세기는 DP 연산과 초기화만 다릅니다. 다음에는 0/1 배낭을 사용해 동일한 합의 부분 집합 분할 문제를 해결합니다.
자주 묻는 질문
“무한 배낭과 동전 교환 II” 강의는 무료인가요?
네 — “무한 배낭과 동전 교환 II” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“무한 배낭과 동전 교환 II”에서 뭘 배우나요?
용량을 정순으로 순회해 항목을 재사용할 수 있도록 하고, 이 변형으로 coin-change-II(방법 수 세기)와 막대 자르기 문제를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“무한 배낭과 동전 교환 II” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 0/1 배낭과 공간 최적화
- 무한 배낭과 동전 교환 II
- 동일한 부분집합 합으로 분할
- 양수와 음수 부호를 사용한 목표 합