무제한 배낭과 동전 교환 DP
항목을 원하는 횟수만큼 사용합니다
무제한 배낭과 동전 교환 DP은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
무제한 항목
무제한 배낭 문제에서는 각 물건을 원하는 만큼 여러 번 선택할 수 있습니다. 정해진 물건 더미가 아니라 자판기의 동전을 생각하면 됩니다.
아주 작은 변화 하나
0/1 배낭 문제와 비교하면 반복문의 방향만 바뀝니다. 무제한 물건에서는 용량을 정방향으로, 즉 작은 값에서 큰 값으로 순회합니다.
정방향 재사용이 핵심
정방향으로 진행하면 dp[w - coin]에 이미 같은 물건이 포함되어 있을 수 있습니다. 이 의도적인 재사용 덕분에 물건을 다시 선택할 수 있습니다.
동전 거스름돈 문제 만나기
고전적인 동전 거스름돈 문제는 어떤 금액을 만들기 위해 필요한 동전 수의 최솟값을 묻습니다. 최댓값 대신 최솟값을 사용하는 무제한 DP입니다.
상태 정의
dp[a]를 금액 a를 만들기 위해 필요한 최소 동전 수라고 합시다. 0은 동전이 필요 없으므로 dp[0] = 0으로 시작합니다.
dp = [float("inf")] * (amount + 1)
dp[0] = 0불가능한 경우 무한대 사용
도달할 수 없는 금액은 처음에 무한대로 둡니다. 마지막까지 어떤 금액이 무한대로 남아 있다면 동전 조합으로 그 금액을 만들 수 없습니다.
전이
각 동전에 대해 그 동전으로 도달할 수 있는 모든 금액을 개선할 수 있는지 확인합니다. 남은 금액의 최솟값에 동전 하나를 더한 값을 사용합니다.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)정방향인 이유
금액을 작은 값에서 큰 값으로 훑으면 dp[a - coin]에 이미 이 동전이 포함될 수 있습니다. 이렇게 해야 하나의 동전이 여러 번 기여할 수 있습니다.
방법의 수 세기
최솟값에 1을 더하는 대신 합을 사용하면 각 금액을 만드는 방법의 수를 셀 수 있습니다. 동전 반복문을 바깥에 두면 순서를 중복해서 세지 않습니다.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]결과 읽기
정답은 dp[amount]에 저장됩니다. 최솟값을 구하는 경우 무한대라는 값은 목표 금액을 만들 수 없다는 뜻입니다.
0/1과 무제한 비교
이 한 가지 전환을 기억하세요. 용량을 역순으로 순회하면 각 물건을 한 번씩만 사용하고, 정방향으로 순회하면 무제한으로 사용합니다. 같은 표를 반대 방향으로 순회하는 것입니다.
빠른 확인
배낭 문제가 무제한이 되는 조건을 확인해 보세요.
복습
무제한 재사용을 위해 반복문을 정방향으로 바꾸고, 최소 동전 수에는 최솟값을, 전체 방법의 수에는 합을 사용하는 동전 거스름돈 문제를 만들었습니다. 💰
자주 묻는 질문
“무제한 배낭과 동전 교환 DP” 강의는 무료인가요?
네 — “무제한 배낭과 동전 교환 DP” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“무제한 배낭과 동전 교환 DP”에서 뭘 배우나요?
항목을 원하는 횟수만큼 사용합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“무제한 배낭과 동전 교환 DP” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 0/1 배낭: 선택하거나 포기하기
- 공간을 최적화한 배낭
- 무제한 배낭과 동전 교환 DP
- 부분집합 합과 분할