그리디 알고리즘(Greedy algorithm) - 동전 지불 문제 | 파이썬

그리디 알고리즘(greedy algorithm) - 동전 지불 문제¶

그리디 알고리즘이란,
쉽게 말해 매 순간 최선의 선택을 하는 알고리즘이다.
전체의 최선이 아닌 매 순간의 최선이기 때문에 전체로 봤을 때는 최선이지 않은 경우가 종종 발생한다.
다시 말해 그리디 알고리즘에서는 2보 전진을 위한 1보 후퇴라는 말은 허용되지 않는다. 오로지 전진만 할 뿐이다.

그리디 알고리즘에 대해 좀 더 자세히 알고 싶다면,
나무위키 - 그리디 알고리즘을 참고하자

동전 지불 문제는
동전의 종류와 지불할 돈이 주어지면,

가장 적은 수의 동전을 사용해 비용을 지불하고,

그 때, 각 동전들이 몇 개 씩 사용되었는지, 잔돈이 생긴다면 잔돈까지 출력하는 코드를 짜는 것이다.

가장 큰 액수의 동전부터 사용해서 점차 작은 단위로 가면 되는

기본적인 그리디 알고리즘 문제이다. 

매 순간 최선의 선택(가장 큰 액수의 동전 사용)이 전체의 최선의 결과(가장 적은 수의 동전 사용)를 가져온다.

 

1. 일반적 접근

이 문제의 기본적인 해결법은 아래와 같다.

# 동전 지불 문제
# 동전 종류, 지불할 돈

coins = [10, 50, 100, 500] # 동전 종류
coins.sort(reverse=True)
toPay = 1352 # 지불할 돈

# normal way

result = {x: 0 for x in coins}

value = toPay

for coin in coins:
	coin_count = value // coin
	value -= coin * coin_count
	result[coin] = coin_count

print(value)
print(result)

2
{500: 2, 100: 3, 50: 1, 10: 0}

 

coins와 toPay는 각각 '동전의 종류'와 '지불할 돈'을 나타낸다.

 

coins.sort(reverse=True)

위에서 처럼 사용자가 동전을 어떤 순서로 입력할 지 알 수 없기 때문에 일단 동전의 종류를 받고, 정렬(sort)해준다. 이때 내림차순(desc)정렬을 위해 (reverse=True)조건을 지정해준다.

 

result = {x: 0 for x in coins}

결과를 나타내기 위해 Dictionary를 선언해준다. 

Dictionary 표현식에 의해 result는 아래와 같이 생성된다.

{500: 0, 100: 0, 50: 0, 10: 0}

value = toPay


for coin in coins:
	coin_count = value // coin
	value -= coin * coin_count
	result[coin] = coin_count

몇 개의 coin을 사용할 지, value 를 coin으로 나눈 몫을 coin_count로 정해주고,

value는 지불할 돈에서 사용한 동전의 값을 빼주며 (앞으로 계산해야 할)남은 돈을 나타내기 위해 toPay의 값을 복사해서 선언했다.

그냥 toPay 변수를 사용해도 현재의 코드에서는 문제가 없지만, 프로그램이 크고 복잡해진다면 원래 지불하고자 했던 값은 따로 저장해둬야 하는 상황이 올 수도 있다. 변수의 용도에 따라 달리 선언하는 습관을 들이면 좋다.

coins(동전 목록)에 있는 coin들을 하나씩 꺼내 비교한다. 이때, 당연히 큰 순서대로 꺼내진다(위에서 sort(reverse)로 정렬했으므로).

result에 coin의 값을 coin_count로 정해준다.

 

2. 또 다른 접근

 

그리디 알고리즘과 동전 지불 문제에 대해서 구글링을 하던 중 재미있는 접근 방법을 보았다. (출처: 곰가드의 라이브러리)

coins = [10, 50, 100, 500]
coins.sort(reverse=True)
toPay = 1352

# Other way

coin_result = {x: 0 for x in coins}

def big_coin(toPay, coins):
    change_list = []
    for coin in coins:
        change_list.append([coin, toPay - coin])
    biggest = change_list[0]
    for change in change_list:
        if biggest[1] >= 0:
            break
        elif biggest[0] > change[0]:
            biggest = change
        
    return biggest

# print(big_coin(2,coins))
        
change = [0, toPay] # [coin, change]
    
while True:
    if change[1] >= coins[-1]:
        change = big_coin(change[1], coins)
        if change[1] > 0:
            coin_result[change[0]] += 1
        else:
            break
    else:
        print(f'change is {change[1]}')
        break
        
print(coin_result)

change is 2
{500: 2, 100: 3, 50: 1, 10: 0}

위 코드는 해당 블로그(곰가드의 라이브러리)에 있는 코드를 내 코드 스타일에 맞게 바꾼 것이다. 기본적인 알고리즘은 같다.

코드를 살펴보면 먼저, big_coin이라는 함수를 만들었다.

# big_coin

coins = [500, 100, 50, 10]

def big_coin(toPay, coins):
    change_list = []
    for coin in coins:
        # change_list = [coin, toPay_last]
        change_list.append([coin, toPay - coin])
    biggest = change_list[0]
    # biggest = [coin, toPay_last]
    for change in change_list:
        if biggest[1] >= 0:
            break
        elif biggest[0] > change[0]:
            biggest = change
            
        
    return biggest

print(big_coin(34,coins))

함수를 설명하면,

먼저 지불할 돈을 모든 동전으로 뺀다. (toPay - coin)

동전 단위화 함께 리스트 형태로 change_list(잔돈 목록)에 저장한다.([coin, toPay - coin])

가장 액수가 큰 동전을 저장하기 위해 biggest변수를 선언하고, change_list[0]을 저장한다.

change_list를 반복하여

잔돈이 있다면(0보다 크거나 같다면), 현재의 biggest값을 리턴하고,

그렇지 않다면(잔돈이 마이너스), 다음(액수가 더 낮은) 동전을 biggest에 저장한다.

 

이 big_coin이라는 함수가 그리디 알고리즘에서 매 순간의 최선의 선택을 위해,

어떤 동전이 최선인지를 판단하는 함수인데

다른 문제라면 가치있는 함수겠지만,

동전 지불 문제에서는 내림차순으로 정렬해주고, 큰 순서로 빼 나가면, 작은 동전들은 굳이 빼지 않아도 되기때문에

모든 동전을 빼주는 것은 불필요하게 처리할 연산을 늘리는 것이다.

 

실제로 처리 속도를 비교해보자.

 

3. 처리 속도 - 일반적 접근 vs big_coin()

# case 1.
coins = [10, 50, 100, 500]
toPay = 1352

# Normal way
2
{500: 2, 100: 3, 50: 1, 10: 0}
time:  0.0005469322204589844

# big_coin()
change is 2
{500: 2, 100: 3, 50: 1, 10: 0}
time:  0.0005698204040527344

의미있는 차이로 보여지진 않는다. 0.00002초의 차이라면 매번 달라질 수 있다. 

지불해야 할 돈 액수를 늘려보았다.

# case 2.
coins = [10, 50, 100, 500]
toPay = 1352678134

무려 100억이 넘는 돈을 동전으로 지불한다... 현실이라면... 끔찍하다..

# Normal way
4
{500: 2705356, 100: 1, 50: 0, 10: 3}
time:  0.45212888717651367

# big_coin()
change is 4
{500: 2705356, 100: 1, 50: 0, 10: 3}
time:  2.2910521030426025

와우.. 수가 커지니 의미있는 차이가 보인다. 약 5배 가량의 처리속도 차이를 보였다.

컴퓨터 성능의 문제를 감안하기 위해 10회 이상의 처리를 거쳤으나 결과는 매번 비슷했다.

 

4. 결론

 

그리디 알고리즘은 위에서 처럼 우리가 최선의 선택을 쉽게 판단할 수 있을 때,

그리고 그 판단들이 전체의 최선의 결과(최적해)를 가져올 수 있을 때 사용하면, 빠른 처리 속도라는 효과를 볼 수 있다.

위에서 언급한 big_coin방식은 결과적으로 모든 동전을 다 지불해 보는 과정이 있기 때문에 그리디 알고리즘이라기 보다는 전체를 탐색하는 알고리즘이라고 볼 수 있다.