탐욕 알고리즘(Greedy) 기초 - 동전 개수 문제

탐욕 알고리즘

: 하나를 결정할 때마다 최적이라고 생각되는 경우를 선택하는 것으로서, 최적의 Solution에 가까운 값을 찾는 알고리즘이다.

 

예를들어 동전이 1 , 2, 5가 있다고 가정하고, 주어진 값은 12이다.

여기서 최적의 해는 5+5+2 = 12 를 구하는 것이다.

 

동전 문제에서 탐욕 알고리즘의 중점은 항상 액수가 제일 큰 동전을 선택한다. 그러나 합이 목표액수를 넘기면 안 된다.

그에 대한 예제로 5원 2개로 10원까지는 만들 수 있으나 3개를 사용하면 12원을 초과하기에 불가능하다.

 

그러나 보통의 생각으로는 5원 2개 2원 1개 사용해서 12원 만들면 되지 않을까라는 생각을 하지만, 여기서는

주어진 갯수의 동전을 모두 사용해야한다는 것이 전제이다. 이에 따라 답을 항상 구할 수 있지는 않다.

 

여기까지의 개념으로 동전 문제를 풀어보자.

Q. 500원, 100원, 50원, 1원이 있다. 4720원을 지불한다고 할 때, 여기서 최소의 동전 수를 구하여라

 

문제 접근의 개념을 먼저 살펴보자.

500원을 먼저 사용해야한다는 것이 탐욕 알고리즘의 핵심이다. 4720원을 지불한다고 할 때, 500원을 9개 사용하면 4500원으로 제일 근접한 값을 얻을 수가 있다. 10개를 사용하면 4720원을 초과하기에 다른 동전을 사용해야한다.

즉, 4720에서 500을 나눠 몫만 구하면 500원짜리를 몇개 사용했는지 구할 수 있다. 

 

그럼 잔액은?

잔액은 주어진 금액 -= 몫(사용 개수) * 사용동전 금액 을 이용하면 된다.

이것이 접근 방법 및 풀이가 되겠다.

 

이제 코드를 통해서 살펴보자.

 

coin_list = [500,100,50,1]

#최종 값, 동전 리스트를 파라메터로 받는다.
def min_coinCount(val, coin_list):
    tot_cnt = 0 # 총 사용한 동전 갯 수
    cnt_list = [] #어떤 동전이 몇번 사용되었는지 세기 위함
    coin_list.sort(reverse = True) #큰 순서대로 정렬, 동전 리스트가 뒤죽박죽 들어가있을 경우 대비
    
    for coin in coin_list:
        cnum = val // coin #몫 (사용 개수) 구하기
        tot_cnt += cnum 
        val -= cnum * coin # 잔액 구하기
        cnt_list.append([coin,cnum]) #결과를 출력하기 위한 리스트에 사용동전과 개수 넣기
        
            
    return tot_cnt, cnt_list
    
print(min_coinCount(4720,coin_list))