(python) 그리디 알고리즘(Greedy Algorithm)-거스름돈 (Feat.백준 11047)

1. 그리디 알고리즘

 

'greedy'란 한국어로 '탐욕스러운'으로 해석이 된다.

 

탐욕스러운 알고리즘? 어떻게 해야 탐욕적인 거지? 등 여러 의문이 생길 수 있다.

 

정리를 하자면 그리디 알고리즘이란 "선택의 순간에서 최적의 선택만을 하는 방법"을 의미한다.

 

단, 매 순간마다 최적의 선택을 하지만 남아 있는 선택들은 고려를 하지 않기 때문에

결과가 항상 최적이라는 보장은 없다.

 

그러므로, 그리디 알고리즘을 사용하기 위해선 조건이 따라붙어야 한다.

 

2. 그리디 알고리즘의 최적해 도달 조건

 

1)  탐욕적 선택 속성(greedy choice property)

탐욕적인 선택이 항상 최적의 해를 보장한다. 즉, 각각의 선택이 서로 영향을 주지 않는다.

 

2) 최적 부분 구조(optimal substructure)

부분 문제들의 최적해들이 모여 전체 문제의 최적해를 구한다.

 

3. 그리디 알고리즘 예제 - 거스름돈

 

윤이는 편의점에 들러 컵라면, 우유, 과자, 초콜릿을 구입하려고 한다.

가격은 총 9260원이 나왔으며 윤이는 현금 10000원을 내면서

직원에게 동전의 개수를 최소한으로 돈을 거슬러 달라고 한다.

 

이때 거스름돈은 740원이며 동전 500원, 100원, 10원으로 구성 가능하다.

 

이러한 경우에 그리디 알고리즘을 사용하여 동전의 액수가 큰 순서인

500원 -> 100원 -> 10원 순으로 선택을 시작한다.

 

1) 500원 선택

740 / 500 = 1 이므로 500원 동전 1개 선택

 

2) 100원 선택

240 / 100 = 2 이므로 100원 동전 2개 선택

 

3) 10원 선택

40 / 10 = 4 이므로 10원 동전 4개 선택

 

결국, 동전의 액수를 내림차순으로 선택하는 것을 최적 선택의 순서라고 보면 된다.

 

4. 예제 적용(백준 11047)

 

백준 11047

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

문제 설명

 

입력된 동전을 최소한으로 선택하여 원하는 금액을 맞춰주는 문제

 

문제 풀이

 

1) 그리디 알고리즘을 사용하기 위하여 동전을 내림차순으로 정렬

 

coin_list = []
for i in range(n):
    coin_list.append(int(input()))
coin_list.sort(reverse=True)

 

2) 각 액수별로 금액을 맞추는 데 사용되는 동전 개수 확인

 

cnt = 0
for coin in coin_list:
    cnt += k // coin
    k = k % coin
    if k == 0:  #금액 맞춤
        break

 

전체코드

 

n, k = map(int, input().split())

coin_list = []
for i in range(n):
    coin_list.append(int(input()))
coin_list.sort(reverse=True)

cnt = 0
for coin in coin_list:
    cnt += k // coin
    k = k % coin
    if k == 0:  #금액 맞춤
        break

print(cnt)