Algorithm Guidecomplexity: O(n)

동전 거스름돈 (Coin Change)

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

01동전 거스름돈 (Coin Change)

알고리즘 작동 원리 탐색

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

500원 ≤ 760 · 500원을 사용합니다. 남은 금액 260원.

100원 ≤ 260 · 100원을 사용합니다. 남은 금액 160원.

100원 ≤ 160 · 한 번 더 사용합니다. 남은 금액 60원.

100원 > 60이라 건너뛰고 50원을 사용합니다. 남은 금액 10원.

10원 ≤ 10 · 마지막 10원을 사용합니다. 남은 금액 0원.

완료 · 동전 5개(500·100·100·50·10)로 760원 완성. 배수 관계 화폐에서는 그리디가 최소 개수를 보장합니다.

remaining760원

coins

500

100

picked · 0

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

1 / 7

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

04 자주 묻는 질문

FAQ

동전 거스름돈 (Coin Change)란 무엇인가요?+

동전 거스름돈 (Coin Change)의 시간복잡도는 어떻게 되나요?+

동전 거스름돈 (Coin Change)의 시간복잡도는 O(n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

동전 거스름돈 (Coin Change)은(는) 어디에 사용하나요?+

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

동전 거스름돈 (Coin Change)를 쉽게 비유하면?+

매 순간 가장 큰 동전을 고릅니다. 동전 체계가 정규적일 때만 최적이고, 그렇지 않으면 최적해를 놓칩니다.

→ 그리디 전체 보기Related

🎯활동 선택 (Activity Selection)

O(n log n)

🎯허프만 코딩 (Huffman Coding)

O(n log n)