파이썬 거스름돈-greedy function

준이는 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

이 문제는 탐욕적(Greedy) 알고리즘을 사용하면 가장 효율적으로 해결할 수 있다. 탐욕 알고리즘은 현재 상황에서 가장 최적의 선택을 하는 방법을 말하는데, 이 문제에서는 가장 큰 단위의 동전부터 거스름돈을 계산해나가는 것이 가장 최소 개수의 동전을 사용하는 방법이다. 500원, 100원, 50원, 10원 순으로 동전을 사용하면 되죠.

---

#1. 탐욕적 함수 (Greedy function)를 사용한 코드

가장 기본적이고 직관적인 코드입니다. greedy_change라는 함수를 만들어서 거스름돈을 계산하는 방식입니다.

def greedy_change(n):
    """
    탐욕적 알고리즘을 이용해 거스름돈 N원에 대한 최소 동전 개수를 계산합니다.
    Args:
        n (int): 거슬러줘야 할 돈 (10의 배수)
    Returns:
        int: 동전의 최소 개수
    """
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += n // coin  # 해당 동전으로 거슬러 줄 수 있는 개수를 더합니다.
        n %= coin         # 거슬러 준 만큼 남은 돈을 갱신합니다.
    return count

# 예시: 거스름돈 1260원에 대한 동전 개수 계산
n = 1260
result = greedy_change(n)
print(f"거스름돈 {n}원에 대한 최소 동전 개수: {result}개")

코드 분석

---

1. 함수 정의 (greedy_change(n))

• def greedy_change(n): : greedy_change라는 이름의 함수를 정의하며, n이라는 인자(parameter)를 받습니다. 여기서 n은 거슬러줘야 할 총 금액을 의미합니다.
• 함수 내의 독스트링(docstring)은 함수의 목적, 인자, 반환 값에 대한 설명을 제공하여 다른 개발자가 코드를 이해하기 쉽게 돕습니다.

2. 변수 초기화

• coins = [500, 100, 50, 10] : 동전의 단위를 큰 금액부터 작은 금액 순으로 정렬한 리스트를 정의합니다. 탐욕적 알고리즘의 핵심은 항상 가장 큰 단위부터 처리하는 것이므로 이 순서가 매우 중요합니다.
• count = 0 : 거슬러줘야 할 동전의 총 개수를 저장할 변수를 0으로 초기화합니다.

3. 반복문 (Loop)을 통한 계산

• for coin in coins: : coins 리스트에 있는 각 동전 단위(500, 100, 50, 10)를 순서대로 반복합니다.
• count += n // coin : 현재 금액 n을 현재 동전 단위 coin으로 나눈 몫을 count에 더합니다. 예를 들어, n이 1260이고 coin이 500일 때, 1260 // 500은 2가 되므로 count는 2가 됩니다. 이는 500원짜리 동전 2개를 사용했다는 의미입니다.
• n %= coin : 현재 금액 n을 현재 동전 단위 coin으로 나눈 나머지로 n을 갱신합니다. 위 예시에서 1260 % 500은 260이므로, 남은 금액은 260원이 됩니다. 다음 반복에서는 260원에 대해 100원짜리 동전 개수를 계산하게 됩니다.

4. 결과 반환

• return count : 모든 동전 단위를 처리한 후, 최종적으로 계산된 동전의 총 개수 count를 반환합니다.

5. 실행 예시

• n = 1260 : 거스름돈으로 1260원을 설정합니다.
• result = greedy_change(n) : greedy_change 함수를 호출하여 계산된 동전 개수를 result 변수에 저장합니다.
• print(...) : 최종 결과를 사용자에게 보여줍니다.

이 코드는 가장 큰 단위의 동전을 최대한 많이 사용하는 전략을 통해 거스름돈을 계산하므로, 주어진 동전 단위(500원, 100원, 50원, 10원)에서는 항상 최적의 해, 즉 최소 개수의 동전을 보장합니다.

 

각 동전의 개수를 포함하여 반환하는 코드

기존 코드에서는 총 동전의 개수만 반환했지만, 이번에는 각 동전(500원, 100원, 50원, 10원)이 몇 개씩 사용되었는지 딕셔너리 형태로 반환합니다.

def greedy_change_with_details(n):
    """
    탐욕적 알고리즘을 이용해 거스름돈 N원에 대한 최소 동전 개수와
    각 동전의 개수를 딕셔너리 형태로 반환합니다.
    Args:
        n (int): 거슬러줘야 할 돈 (10의 배수)
    Returns:
        dict: 각 동전의 개수와 총 동전 개수가 포함된 딕셔너리
    """
    coins = [500, 100, 50, 10]
    result = {
        'total_count': 0,
        '500_won': 0,
        '100_won': 0,
        '50_won': 0,
        '10_won': 0
    }
    
    for coin in coins:
        num_coins = n // coin  # 해당 동전으로 거슬러 줄 수 있는 개수
        result['total_count'] += num_coins
        
        # 동전 단위에 따라 딕셔너리에 개수 저장
        if coin == 500:
            result['500_won'] = num_coins
        elif coin == 100:
            result['100_won'] = num_coins
        elif coin == 50:
            result['50_won'] = num_coins
        elif coin == 10:
            result['10_won'] = num_coins
        
        n %= coin  # 남은 돈 갱신
        
    return result

# 예시: 거스름돈 1260원에 대한 동전 개수 계산
n = 1260
change_details = greedy_change_with_details(n)

print(f"거스름돈 {n}원에 대한 거스름돈 내역:")
print(f"총 동전 개수: {change_details['total_count']}개")
print(f"500원 동전: {change_details['500_won']}개")
print(f"100원 동전: {change_details['100_won']}개")
print(f"50원 동전: {change_details['50_won']}개")
print(f"10원 동전: {change_details['10_won']}개")

코드 분석

이 코드는 다음과 같은 단계로 거스름돈을 계산합니다.

• 함수 정의 및 변수 초기화: greedy_change_with_details(n) 함수는 거스름돈 금액 n을 입력받습니다. coins = [500, 100, 50, 10] 리스트는 동전 단위를 내림차순으로 정의하며, 이 순서가 탐욕 알고리즘의 핵심입니다. result 딕셔너리는 total_count와 각 동전 개수를 저장하는 용도로 초기화됩니다.
• 반복문과 계산: for coin in coins:를 통해 가장 큰 단위인 500원부터 10원까지 순서대로 계산을 진행합니다.
  • num_coins = n // coin: 현재 남은 금액 n을 현재 동전 coin으로 나눈 몫을 계산합니다. 이 몫은 해당 동전을 몇 개 사용해야 하는지를 의미합니다.
  • result['total_count'] += num_coins: 계산된 동전 개수를 총 개수에 더합니다.
  • if...elif... 조건문: 각 coin 값에 맞춰 result 딕셔너리의 해당 키('500_won', '100_won' 등)에 num_coins 값을 저장합니다. 이 부분이 각 동전별 개수를 따로 기록하는 로직입니다.
  • n %= coin: 현재 동전을 거슬러주고 남은 금액을 n에 다시 저장합니다. 다음 반복에서는 이 갱신된 n 값으로 다음 동전 단위에 대한 계산을 이어갑니다.
• 결과 반환: 모든 반복이 끝나면, 각 동전 개수와 총 동전 개수가 모두 담긴 result 딕셔너리를 반환합니다.

이 코드는 명확한 변수명과 딕셔너리라는 적절한 데이터 구조를 사용하여, 단순한 총 개수뿐만 아니라 각 동전의 상세 내역까지 가독성 높게 정리해서 보여주는 장점이 있습니다.

 

---

 

탐욕적 알고리즘의 원리

이 문제에서 탐욕적 알고리즘이 항상 최적의 해를 보장하는 이유는, 동전의 단위가 서로 배수 관계에 있기 때문입니다. 즉, 10원 5개로 50원을 만들 수 있고, 50원 2개로 100원을 만들 수 있으며, 100원 5개로 500원을 만들 수 있습니다. 이러한 구조 덕분에 가장 큰 단위의 동전부터 처리하는 것이 항상 최소 개수를 보장합니다.

만약 동전 단위가 10원, 30원, 40원이었다면 어떨까요? 거스름돈 80원을 준다고 할 때, 40원 2개를 주는 것이 가장 적은 동전 개수입니다. 하지만 탐욕적 알고리즘은 40원 1개, 30원 1개, 10원 1개를 주어 총 3개의 동전을 사용하게 되죠. 이처럼 탐욕 알고리즘이 항상 최적의 해를 보장하지는 않지만, 현재 문제처럼 동전 단위가 서로 배수 관계인 경우에는 완벽하게 작동합니다.