[정글 베이직28]그리디 알고리즘 - 거스름돈

매 순간 가장 큰 동전부터 최대한 사용하는 그리디 알고리즘의 대표 입문 문제

문제 한눈에 보기

입력	거슬러줄 금액 change, 동전 종류 coins
출력	총 동전 개수와 동전별 사용 개수
핵심 전략	가장 큰 단위 동전부터 최대한 많이 사용
예시	1260원 → 500원 2개, 100원 2개, 50원 1개, 10원 1개 = 총 6개

핵심 1

현재 순간에 가장 큰 동전을 쓰는 것이 이득이라고 판단하고 바로 선택한다.

핵심 2

change // coin 으로 현재 동전 개수를 바로 구할 수 있다.

핵심 3

나머지 금액은 change % coin 으로 갱신한다.

왜 그리디가 통하나?

500원, 100원, 50원, 10원처럼 단위가 규칙적인 동전 체계에서는 큰 동전을 먼저 쓰는 것이 전체 동전 수를 줄이는 데 유리하다.

다만 모든 동전 체계에서 항상 그리디가 정답은 아니다. 예를 들어 동전 종류가 이상하게 주어지면 DP가 필요한 경우도 있다.

최종 코드

def make_change_greedy(change, coins):
    result = {}
    total_coins = 0

    for coin in coins:
        cnt = change // coin
        change = change % coin

        if cnt > 0:
            result[coin] = cnt
            total_coins += cnt

    return total_coins, result

한 줄씩 설명

줄	코드	설명
1	result = {}	각 동전을 몇 개 썼는지 저장할 딕셔너리다.
2	total_coins = 0	총 동전 개수를 세는 변수다.
4	for coin in coins:	큰 동전부터 차례대로 본다.
5	cnt = change // coin	현재 동전으로 몇 개까지 줄 수 있는지 계산한다.
6	change = change % coin	그 동전을 쓰고 남은 금액으로 갱신한다.
8-10	if cnt > 0: result[coin] = cnt total_coins += cnt	0개보다 많이 썼다면 결과에 기록하고 총 개수에 더한다.
12	return total_coins, result	최종 결과 반환.

예시 시뮬레이션

change = 1260, coins = [500, 100, 50, 10]

동전	사용 개수	남은 금액
500	2	260
100	2	60
50	1	10
10	1	0

총 6개가 된다.

자주 하는 실수

• 동전 배열이 큰 순서로 정렬되어 있지 않으면 그리디 전략이 깨질 수 있다.
• total_coins += result[coin] 도 맞지만, 더 직접적으로는 total_coins += cnt 가 읽기 쉽다.
• 모든 동전 체계에서 그리디가 정답이라고 착각하면 안 된다.

시간복잡도

동전 종류 수를 k라고 하면 O(k)

공간복잡도

결과 딕셔너리 저장으로 O(k)

한 문장 정리

거스름돈 문제는 현재 가장 큰 동전부터 최대한 많이 쓰고 남은 금액을 줄여 나가는 그리디의 전형적인 예제다.