Algorithm Guidecomplexity: O(n)
동전 거스름돈 (Coin Change)
가장 큰 동전부터 욕심껏 사용해 거스름돈을 만드는 그리디 전략입니다. 화폐 단위가 배수 관계(예: 500·100·50·10)일 때 최적이지만, 일반적인 단위에서는 최소 개수를 보장하지 못합니다.
01 알고리즘 작동 원리 탐색
Interactive Step-by-StepHOVER OR SCROLL
Coin Change · target=760
remaining760원
coins
500
100
50
10
picked · 0
거스름돈 760원을 만듭니다. 가장 큰 동전부터 욕심껏(greedy) 사용합니다.
Logic Node1 / 7
Live Python
02 쉽게 이해하기
For Everyone🔑비유
거스름돈을 줄 때 큰 동전부터 꺼내 금액을 빨리 줄이는 습관과 같습니다.
💡쉽게 말하면
매 순간 쓸 수 있는 가장 큰 동전을 욕심껏 고릅니다.
화폐가 배수 관계면 최소 개수가 보장되지만, 일반적인 단위에서는 실패할 수도 있어요.
📍어디에 쓰나
- –거스름돈 계산
- –단위가 정해진 자원 배분
03 파이썬 구현 코드
동전 거스름돈 (Coin Change)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.
core_implementation.py
04 자주 묻는 질문
FAQ동전 거스름돈 (Coin Change)란 무엇인가요?+
가장 큰 동전부터 욕심껏 사용해 거스름돈을 만드는 그리디 전략입니다. 화폐 단위가 배수 관계(예: 500·100·50·10)일 때 최적이지만, 일반적인 단위에서는 최소 개수를 보장하지 못합니다.
동전 거스름돈 (Coin Change)의 시간복잡도는 어떻게 되나요?+
동전 거스름돈 (Coin Change)의 시간복잡도는 O(n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.
동전 거스름돈 (Coin Change)은(는) 어디에 사용하나요?+
거스름돈 계산, 단위가 정해진 자원 배분.
동전 거스름돈 (Coin Change)를 쉽게 비유하면?+
거스름돈을 줄 때 큰 동전부터 꺼내 금액을 빨리 줄이는 습관과 같습니다.
→ 그리디 전체 보기Related
Guide Progress0%