[알고리즘] 그리디(Greedy) 알고리즘(거스름돈 문제 소스코드)

안녕하세요, 이번 포스팅에서는 지난 포스팅에서 다룬 그리디 알고리즘 연습문제의 소스코드를 공유합니다.

heytech.tistory.com/44

[알고리즘] 그리디(Greedy) 알고리즘에 대해 알아보자! (연습문제 포함)

1.  연습문제

그리디 알고리즘의 가장 대표적인 예시 문제는 거스름돈 계산 문제입니다.

Q.  당신은 카페의 계산을 도와주는 직원이며 카운터에는 거스름돈으로 사용하는 화폐로서 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정한다. 손님에게 제공해야 할 돈이 R일 때 거슬러 줄 수 있는 동전의 최소 개수를 구하는 코드를 작성하시오. 단, 거슬러 주는 돈 R은 항상 10의 배수이다.

입력 예시 1

460

출력 예시

6

---

2.  소스코드

# 거스름돈을 입력받습니다.
while (True):
    r = input("거스름돈을 입력하세요")
    # 거스름돈은 항상 10의 배수로 입력받음
    if (r%10 == 0):
        break
    else:
        print("거스름돈을 10의 배수로 입력하세요")
# 거스름돈의 동전의 개수
coin_num = 0

coin_types = [500, 100, 50, 10]

# 가장 큰 화폐부터 차례로 돈을 거슬러주는 방식
for coin in coin_types:
    # 해당 동전으로 제공할 수 있는 동전의 개수
    coin_num += n//coin
    # 해당 동전으로 제공하고 남은 나머지 잔돈
    r%=coin

print(coin_num)

이번 문제에서는 가장 큰 화폐 단위의 동전을 활용해 돈을 거슬러 주는 것과 같은 '탐욕적인' 문제 해결 방식을 활용하였습니다.

먼저, 동전 단위를 저장할 리스트를 정의하고, 이 리스트의 원소 개수만큼 반복문을 수행하며 화폐 단위가 큰 동전부터 가장 작은 동전까지 차례대로 거스름돈을 계산하는 방식을 채택하였습니다.

입력 예시 1

1460

출력 예시1

8

입력 예시 2

1260

출력 예시 2

6

2.  그리디 알고리즘 활용의 정당성 검토

지난 포스팅에서 그리디 알고리즘을 통해 '최적의 해'를 찾는 해법이 정당한지 검토해야 한다고 말씀드렸습니다.

위와 같이 거스름돈 문제를 그리디 알고리즘을 통해 풀 수 있는 이유는 무엇일까요?

바로 큰 단위의 동전은 항상 작은 단위의 동전의 배수이기 때문입니다.

작은 단위의 동전들만 조합할 경우에는 '거슬러 줄 수 있는 동전의 최소 개수'라는 '최적의 해'를 구할 수 없기 때문입니다.

---

그럼 오늘도 즐거운 하루 보내시길 바랍니다.

고맙습니다^^