Algorithm Guidecomplexity: O(n)

동전 거스름돈 (Coin Change)

가장 큰 동전부터 욕심껏 사용해 거스름돈을 만드는 그리디 전략입니다. 화폐 단위가 배수 관계(예: 500·100·50·10)일 때 최적이지만, 일반적인 단위에서는 최소 개수를 보장하지 못합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Coin Change · target=760

remaining760원

coins

500

100

picked · 0

거스름돈 760원을 만듭니다. 가장 큰 동전부터 욕심껏(greedy) 사용합니다.

Logic Node1 / 7

Live Python

1def coin_change_greedy(coins, amount):

2 coins = sorted(coins, reverse=True)

3 result = []

4 for coin in coins:

5 while amount >= coin:

6 amount -= coin

7 result.append(coin)

8 return result if amount == 0 else None

02 쉽게 이해하기

For Everyone

🔑비유

거스름돈을 줄 때 큰 동전부터 꺼내 금액을 빨리 줄이는 습관과 같습니다.

💡쉽게 말하면

매 순간 쓸 수 있는 가장 큰 동전을 욕심껏 고릅니다.

화폐가 배수 관계면 최소 개수가 보장되지만, 일반적인 단위에서는 실패할 수도 있어요.

📍어디에 쓰나

–거스름돈 계산
–단위가 정해진 자원 배분

03 파이썬 구현 코드

동전 거스름돈 (Coin Change)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else None

Guide Progress0%