Chapter 3. 그리디 알고리즘, 거스름돈 문제

📌그리디 알고리즘

그리디 알고리즘 = 탐욕법

현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

기준에 따라 좋은 것을 선택하는 알고리즘이므로 '가장 큰 순서대로', '가장 작은 순서대로' 같은 기준을 문제에서 제시해준다. 정렬 알고리즘과 짝을 이뤄 자주 출제된다.

 

📌문제

예제 3-1 거스름돈

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

 

📌풀이

'가장 큰 화폐 단위부터' 돈을 거슬러 준다.

500원짜리 N개 → 100원짜리 N개 → 50원짜리 N개 → 10원짜리 N개

 

📌코드

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500,100,50,10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin
    
print(count)

 

동전의 개수: // 연산자를 사용해서 남은 거스름돈을 화폐 단위로 나눈 몫을 구함.

남은 거스름돈 업데이트: 거스름돈을 화폐 단위로 나눈 나머지를 구함.

 

화폐의 종류만큼 반복을 진행하므로 화폐의 종류를 K개라고 할 때, 시간 복잡도는 O(K)

 

📌참고

이것이 취업을 위한 코딩 테스트다 with 파이썬

이것이 취업을 위한 코딩 테스트다 with 파이썬