7-2. 그리디: 거스름돈 문제

1. 그리디 알고리즘과 거스름돈 문제의 만남

그리디(Greedy) 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결하는 알고리즘 설계 패러다임입니다. 마치 눈앞의 이익만을 좇는 탐욕스러운(greedy) 방식과 유사하여 이러한 이름이 붙었습니다. 그리디 알고리즘은 최적 해를 보장하지 않는 경우가 많지만, 몇몇 특정 문제에서는 놀랍도록 효과적입니다. 이러한 문제들을 '그리디 알고리즘으로 풀 수 있는 문제'라고 부릅니다.

거스름돈 문제는 우리 일상생활에서 쉽게 접할 수 있는 문제입니다. 주어진 금액을 거슬러주기 위해 최소한의 동전(혹은 지폐) 개수를 사용하는 방법은 직관적으로 그리디 알고리즘이 적용될 수 있는 대표적인 예시입니다.

1) 그리디 알고리즘의 기본 아이디어

그리디 알고리즘은 문제를 해결하기 위한 일련의 단계를 거칩니다. 각 단계에서 현재 시점에서 가장 "좋은" 선택을 합니다. 이 "좋은" 선택은 문제의 특성에 따라 다르게 정의됩니다. 거스름돈 문제에서는 가장 큰 가치의 동전부터 사용하여 잔돈을 만드는 것이 '좋은' 선택이 됩니다.

2) 왜 그리디 알고리즘이 효과적일까?

그리디 알고리즘이 효과적인 이유는 문제의 특정한 구조 때문입니다. 거스름돈 문제의 경우, 큰 동전부터 사용하는 것이 항상 최적 해를 보장합니다. 이는 동전의 가치가 서로 배수 관계에 있기 때문입니다. (예: 1원, 10원, 100원, 500원)

2. 거스름돈 문제의 그리디 접근법

거스름돈 문제를 그리디 알고리즘으로 해결하는 방법은 간단합니다.

1. 가장 큰 가치의 동전부터 시작합니다.
2. 현재 잔액에서 해당 동전의 가치를 뺄 수 있다면, 뺄 수 있는 만큼 뺍니다.
3. 다음으로 작은 가치의 동전으로 이동하여 2단계를 반복합니다.
4. 잔액이 0이 되면 종료합니다.

1) 알고리즘의 예시

예를 들어, 480원을 거슬러줘야 한다고 가정해 보겠습니다.

1. 500원: 480원 < 500원 이므로 500원 사용 불가.
2. 100원: 480원 > 100원, 480 - 100 380원, 100원 4개 사용.
3. 50원: 380원 > 50원, 380 - (50 * 7) 30원, 50원 7개 사용.
4. 10원: 30원 > 10원, 30 - 10 20원, 10원 2개 사용.
5. 1원: 20원 > 1원, 20 - 1 19원, 1원 19개 사용.

위 과정을 통해 480원을 거슬러주기 위해 100원 4개, 50원 7개, 10원 2개, 1원 19개 총 32개의 동전이 필요하다는 것을 알 수 있습니다. 이 예시에서는 50원짜리 동전을 7개가 아닌 3개만 사용하는 것이 최적의 해를 보장합니다. 하지만 일반적인 경우 (1, 10, 100, 500원)의 동전의 조합에서는 그리디 알고리즘이 최적의 해를 보장합니다.

2) 알고리즘의 시각화

다음은 거스름돈 문제 해결 과정을 시각적으로 표현한 플로우 차트입니다.

3. 최적성 증명: 그리디 알고리즘이 최적 해를 보장하는 이유

거스름돈 문제에서 그리디 알고리즘이 최적 해를 보장하는 이유는 특정 동전 가치들의 독특한 관계 때문입니다. 일반적으로 사용되는 동전의 가치 (1, 5, 10, 50, 100, 500)는 서로 배수 관계를 이루고 있습니다. 이는 큰 가치의 동전을 작은 가치의 동전으로 대체할 때, 동전의 개수가 늘어나지 않거나 최소한 유지되도록 합니다.

1) 배수 관계의 중요성

배수 관계가 아닌 동전 가치가 존재하는 경우, 그리디 알고리즘은 최적 해를 보장하지 못할 수 있습니다. 예를 들어, 동전의 가치가 1, 7, 10인 경우를 생각해 봅시다. 14원을 거슬러주어야 한다면, 그리디 알고리즘은 10원 1개와 1원 4개를 사용하여 총 5개의 동전을 사용합니다. 그러나 최적 해는 7원짜리 동전 2개를 사용하는 것입니다.

2) 수학적 증명 (간단한 예시)

명제: 동전의 가치가 $c_1, c_2, ..., c_n$이고, $c_i$는 $c_{i-1}$의 배수라고 가정합니다. 이때, 그리디 알고리즘은 모든 잔돈에 대해 최소한의 동전 개수를 사용한다.

증명 (귀납법):

• 기저 사례: 잔돈이 $c_1$ 이하일 경우, 그리디 알고리즘은 정확히 $c_1$ 동전을 사용합니다. 이는 최적 해입니다.
• 귀납적 가정: 잔돈 $k$에 대해, 그리디 알고리즘이 최소 개수의 동전을 사용한다고 가정합니다.
• 귀납적 단계: 잔돈 $k + c_i$에 대해 생각해 봅시다. 그리디 알고리즘은 먼저 $c_i$ 동전을 최대한 많이 사용합니다. 만약 그리디 알고리즘이 $c_i$ 동전을 사용하는 것보다 더 적은 수의 동전으로 $k + c_i$를 만들 수 있다면, $c_i$ 동전을 사용하지 않은 채로 $k + c_i$를 만드는 경우도 존재해야 합니다. 하지만, $c_i$는 $c_{i-1}$의 배수이므로, $c_i$를 다른 동전으로 대체하면 동전의 개수가 늘어나거나 같아집니다. 따라서 그리디 알고리즘은 최소 개수의 동전을 사용합니다.

4. 코드 구현 및 예시

그리디 알고리즘을 사용한 거스름돈 문제의 간단한 파이썬 코드 예시입니다.

def greedy_coin_change(amount, coins):
    """
    그리디 알고리즘을 사용하여 거스름돈을 계산합니다.

    Args:
        amount: 거스름돈으로 줄 금액 (정수).
        coins: 사용 가능한 동전의 가치 목록 (내림차순 정렬).

    Returns:
        동전의 개수를 담은 딕셔너리. 각 동전의 가치를 키로, 사용된 동전의 개수를 값으로 가짐.
        잔돈을 만들 수 없는 경우 None을 반환.
    """
    coin_count = {}
    remaining_amount = amount

    for coin in coins:
        if remaining_amount >= coin:
            num_coins = remaining_amount // coin # 정수 나누기
            coin_count[coin] = num_coins
            remaining_amount -= coin * num_coins

    if remaining_amount == 0:
        return coin_count
    else:
        return None # 잔돈을 만들 수 없는 경우

# 예시
coins = [500, 100, 50, 10, 5, 1]
amount = 480
result = greedy_coin_change(amount, coins)

if result:
    print("거스름돈:")
    for coin, count in result.items():
        print(f"{coin}원: {count}개")
else:
    print("잔돈을 만들 수 없습니다.")

1) 코드 설명

• greedy_coin_change(amount, coins) 함수는 주어진 금액(amount)과 사용 가능한 동전 목록(coins)을 입력으로 받습니다.
• coins 리스트는 내림차순으로 정렬되어 있어야 합니다.
• 함수는 각 동전의 가치에 대해 가능한 한 많은 동전을 사용하고, 남은 금액을 업데이트합니다.
• 결과로 각 동전의 개수를 담은 딕셔너리를 반환합니다. 잔돈을 만들 수 없는 경우 None을 반환합니다.

2) 실행 결과

위 코드 예시를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

거스름돈:
100원: 4개
50원: 1개
10원: 3개

5. 주의사항 및 실용적인 고려 사항

1) 그리디 알고리즘의 한계

앞서 언급했듯이, 그리디 알고리즘은 항상 최적 해를 보장하지 않습니다. 특히 동전의 가치가 특정한 배수 관계를 이루지 않는 경우에는 다른 알고리즘(예: 동적 프로그래밍)을 고려해야 합니다.

2) 실제 환경에서의 문제점

실제 환경에서는 동전의 종류, 재고, 손상된 동전, 그리고 환율 변동과 같은 다양한 요소를 고려해야 합니다. 또한, 효율적인 알고리즘 구현과 함께 사용자의 편의성을 고려한 인터페이스 디자인도 중요합니다.

3) 성능 최적화

• 동전 목록 정렬: 그리디 알고리즘은 동전 목록이 내림차순으로 정렬되어 있을 때 효율적으로 작동합니다. 정렬되지 않은 경우, 사전에 정렬하는 과정을 거쳐야 합니다.
• 계산 속도: 정수 나눗셈 연산(//)은 비교적 빠르게 수행되므로, 알고리즘의 주요 성능 병목 지점은 아닙니다. 그러나 매우 큰 금액을 처리하는 경우에는 자료형의 크기를 고려해야 합니다.

6. 결론

거스름돈 문제는 그리디 알고리즘을 이해하고 적용하는 데 매우 유용한 예시입니다. 그리디 알고리즘의 기본적인 아이디어를 파악하고, 최적 해를 보장하는 조건(동전 가치의 배수 관계)을 이해하는 것은 중요합니다. 또한, 코드 구현을 통해 알고리즘의 동작 방식을 직접 확인하고, 실제 문제에 적용하는 연습을 해보는 것이 좋습니다. 마지막으로, 그리디 알고리즘의 한계와 다른 알고리즘과의 비교를 통해 문제 해결 능력을 향상시킬 수 있습니다.