동전 교환 시각화
주어진 동전으로 목표 금액을 만드는 최소 동전 수를 DP로 구하는 과정을 학습하세요
동적 프로그래밍★☆☆
속도
1 / 1최소 동전 수: -선택된 동전: -
프리셋
계산 완료갱신됨역추적불가능 (INF)
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
동전 교환이란?
주어진 동전 종류로 목표 금액을 만드는 최소 동전 수를 구하는 대표적인 DP 문제입니다. 그리디로는 최적해를 보장할 수 없어 DP가 필요합니다.
사용 방법
- 1사용 가능한 동전 종류와 목표 금액을 설정하세요
- 2실행하면 DP 배열이 채워지는 과정을 관찰할 수 있습니다
- 3각 금액에 대해 어떤 동전이 선택되는지 역추적으로 확인하세요
- 4동전 종류를 변경하여 다양한 케이스를 실험해보세요
동작 원리
- 1dp[i] = 금액 i를 만드는 최소 동전 수, dp[0] = 0
- 2각 금액 i에 대해: dp[i] = min(dp[i - coin] + 1) for each coin ≤ i
- 3dp[amount]가 최종 답, ∞이면 불가능
- 4시간 O(amount × coins), 공간 O(amount)
실무 활용
- •자판기/ATM의 거스름돈 최적화
- •결제 시스템의 최소 지폐/동전 조합
- •리소스 할당 문제의 기본 모델
- •코딩 면접 필수 문제 — 탑다운/바텀업 DP 연습
비슷한 알고리즘
- •배낭 문제 — 무게 제한 + 가치 최대화, 동전 교환은 수량 제한 없는 특수 케이스
- •그리디 거스름돈 — 특정 동전 체계(1, 5, 10, 50, ...)에서만 최적, 일반적으로 실패
- •동전 조합 수 — 최소 수가 아닌 가능한 조합의 '수'를 세는 변형
학습 팁
- •[1, 3, 4]로 금액 6을 만드는 예시부터 시작하세요 — 그리디(4+1+1)는 3개, DP(3+3)는 2개
- •dp 배열을 직접 채워보고 시각화와 대조하세요
- •탑다운(재귀+메모이제이션)과 바텀업 두 가지로 구현해보세요
자주 묻는 질문
Q. 그리디로 안 되나?
A. 특수한 동전 체계(예: 한국 원화)에서만 됩니다. 일반적으로 DP가 필요합니다.
Q. 동전 수량 제한이 있으면?
A. 제한 배낭 문제(Bounded Knapsack)로 확장됩니다.