[파이썬/동적계획법] 동전 거스름돈 계산

최근 7일 통계 중에 배낭 문제가 1위길래...
옛 글을 다시 읽어보니...
동전 거스름돈을 언급만 하고...
풀지 않았더군요.  

https://comdoc.tistory.com/entry/35-%EB%B0%B0%EB%82%AD%EB%AC%B8%EC%A0%9CKnapsack-problem-%ED%8C%8C%EC%9D%B4%EC%8D%AC

그리디는 간단해서 원문에 추가했습니다만...
그 외는 내용이 많아서 새 포스트로 올려봅니다.

 

1. 그리디 알고리듬(탐욕법)

우리나라 동전은 500, 100, 50, 10, 5, 1원이 있습니다.  
이 상황에서는 그리디 알고리듬으로 문제를 풀 수 있습니다.
각 단계에서 최선의 값을 구하는 것이 전체적으로도 맞는 답이 됩니다. 

* 간략한 코드를 위해 동전은 크기가 큰 순서대로 리스트에 담겨 제공된다고 합시다. 

def count_changes(coins, money):
    changes = []
    for coin in coins:
        changes.append(money // coin)
        money %= coin
    return changes


print(count_changes([500, 100, 50, 10, 5, 1], 2025))  # [4, 0, 0, 2, 1, 0]

 

그런데, 만약 321원짜리 동전이 있다면...
아주 난감합니다.

 

2. 깊이 우선 탐색

for 문을 이용해 모든 경우의 수를 찾아보았습니다. (brute force)

* 동전은 무한히 준비되어 있습니다. 

이 코드는 너무 오래 걸립니다.

def count_changes(coins, money):
    min_changes = money
    for num_500 in range(money // coins[0] + 1):  # num_500: 500원 동전 개수
        for num_321 in range(money // coins[1] + 1):
            for num_100 in range(money // coins[2] + 1):
                for num_50 in range(money // coins[3] + 1):
                    for num_10 in range(money // coins[4] + 1):
                        for num_5 in range(money // coins[5] + 1):
                            for num_1 in range(money // coins[6] + 1):
                                total = sum((num_500 * coins[0],
                                             num_321 * coins[1],
                                             num_100 * coins[2],
                                             num_50 * coins[3],
                                             num_10 * coins[4],
                                             num_5 * coins[5],
                                             num_1,
                                             ))
                                if total == money:
                                    changes = sum((num_500,
                                                   num_321,
                                                   num_100,
                                                   num_50,
                                                   num_10,
                                                   num_5,
                                                   num_1,
                                                   ))
                                    min_changes = min(changes, min_changes)
    return min_changes


print(count_changes([500, 321, 100, 50, 10, 5, 1], 2025))

for문을 살펴보면
500원 동전 0개(num_500 == 0)를 시작으로 for가 시작되어....
모든 동전이 0개인 경우 합계(total)를 계산해서 조건문과 일치하는지 확인하고... 
그 다음은 1원의 개수가 1개 나머지 동전은 0개.....
그 다음은 1원 개수가 2개 나머지 동전은 0개.....
...
그 다음은 1원 개수가 2025개 나머지 동전은 0개.....
그 다음은 1원 개수가 0개, 5원 개수가 1개, 나머지 동전은 0개....
...
이런 식으로 반복됨을 알 수 있습니다.  

이런 식으로 노드들을 방문하는 방식을 '깊이 우선 탐색'이라고 합니다.
(이 문제를 푸는 데 중요한 건 아닌데 알고 계시면 좋을 것 같아서...)

 

마지막에 모아서 계산했던
동전 수의 합과 잔돈 금액의 합을 
조금씩 나눠서 계산해 봅니다. 

정확하게 말씀드리자면
거스름돈 총액에서
방문한 트리의 동전 금액을 빼주었습니다. 

이렇게 했더니
각 for문의 range도 줄여줄 수 있게 되었네요. 

이전 코드 보단 꽤 빨라졌습니다.
(기다리면 결과는 볼 수 있습니다. ㅎㅎ)

def count_changes(coins, money):
    min_changes = money
    for num_500 in range(money // coins[0] + 1):
        total1 = money - coins[0] * num_500
        changes1 = num_500
        for num_321 in range(total1 // coins[1] + 1):
            total2 = total1 - coins[1] * num_321
            changes2 = changes1 + num_321
            for num_100 in range(total2 // coins[2] + 1):
                total3 = total2 - coins[2] * num_100
                changes3 = changes2 + num_100
                for num_50 in range(total3 // coins[3] + 1):
                    total4 = total3 - coins[3] * num_50
                    changes4 = changes3 + num_50
                    for num_10 in range(total4 // coins[4] + 1):
                        total5 = total4 - coins[4] * num_10
                        changes5 = changes4 + num_10
                        for num_5 in range(total5 // coins[5] + 1):
                            total6 = total5 - coins[5] * num_5
                            changes6 = changes5 + num_5
                            for num_1 in range(changes6 // coins[6] + 1):
                                total7 = total6 - num_1
                                changes7 = changes6 + num_1

                                if total7 == 0:
                                    min_changes = min(changes7, min_changes)
    return min_changes


print(count_changes([500, 321, 100, 50, 10, 5, 1], 2025))

 

시간을 단축하기 위해 조건문을 몇 개 추가합시다. 

total(거스름돈의 총액에서 동전들을 차감한 금액)이 음수가 되거나,
changes(거스름돈 동전의 개수)가 앞서 계산했던 최솟값을 넘어간 경우는
더 아래의 for문을 진행하더라도 답이 나오지 않습니다.

따라서 더 아래의 for 문들을 'continue'명령으로 skip 하면 좋습니다. 

그리고 중간에 total == 0 인 결과가 나온 경우,
답을 찾았기 때문에 더 아래의 for문을 진행할 필요가 없으니,
답을 정리하고 continue 해줍니다. 

이 두 조건문을 각 단계마다 추가해 줍니다. 

def count_changes(coins, money):
    min_changes = money
    for num_500 in range(money // coins[0] + 1):
        total1 = money - coins[0] * num_500
        changes1 = num_500
        if total1 < 0 or changes1 > min_changes:
            continue
        if total1 == 0:
            min_changes = min(changes1, min_changes)
            continue
        for num_321 in range(total1 // coins[1] + 1):
            total2 = total1 - coins[1] * num_321
            changes2 = changes1 + num_321
            if total2 < 0 or changes2 > min_changes:
                continue
            if total2 == 0:
                min_changes = min(changes2, min_changes)
                continue
            for num_100 in range(total2 // coins[2] + 1):
                total3 = total2 - coins[2] * num_100
                changes3 = changes2 + num_100
                if total3 < 0 or changes3 > min_changes:
                    continue
                if total3 == 0:
                    min_changes = min(changes3, min_changes)
                    continue
                for num_50 in range(total3 // coins[3] + 1):
                    total4 = total3 - coins[3] * num_50
                    changes4 = changes3 + num_50
                    if total4 < 0 or changes4 > min_changes:
                        continue
                    if total4 == 0:
                        min_changes = min(changes4, min_changes)
                        continue
                    for num_10 in range(total4 // coins[4] + 1):
                        total5 = total4 - coins[4] * num_10
                        changes5 = changes4 + num_10
                        if total5 < 0 or changes5 > min_changes:
                            continue
                        if total5 == 0:
                            min_changes = min(changes5, min_changes)
                            continue
                        for num_5 in range(total5 // coins[5] + 1):
                            total6 = total5 - coins[5] * num_5
                            changes6 = changes5 + num_5
                            if total6 < 0 or changes6 > min_changes:
                                continue
                            if total6 == 0:
                                min_changes = min(changes6, min_changes)
                                continue
                            for num_1 in range(changes6 // coins[6] + 1):
                                total7 = total6 - num_1
                                changes7 = changes6 + num_1
                                if total7 == 0:
                                    min_changes = min(changes7, min_changes)
                                    continue
    return min_changes


print(count_changes([500, 321, 100, 50, 10, 5, 1], 2025))

range(money // coins[0] + 1) 보다는
range(money // coins[0], -1, -1) 의 순서로
탐색하는 것이 더 빠릅니다.  

빨리 최솟값을 찾으면,
계산하지 않고 넘어가는(=continue) 부분이 많아집니다. 

 

조건문을 각 단계에 넣었더니 반복되는 코드들이 보입니다.
반복되는 코드들을 남겨두면,
가독성은 떨어지고, 실수의 확률은 올라갑니다. 

반복을 줄여야 합니다.

프로그래머는 반복을 줄이는 일을 하는 사람입니다!

위 코드의 경우,
재귀를 이용해 반복되는 코드들을 정리하는 것이 가장 쉬워 보입니다.

def count_changes(coins, money):
    min_changes = money
    len_coins = len(coins)

    def recursive(total, changes, coins_index):
        nonlocal min_changes
        if total == 0:
            min_changes = min(changes, min_changes)
            return
        if total < 0 or changes > min_changes or coins_index == len_coins:
            return
        coin_type = coins[coins_index]
        for coins_num in range(total // coin_type, -1, -1):
            recursive(total - coin_type * coins_num, changes + coins_num, coins_index + 1)

    recursive(money, 0, 0)
    return min_changes


print(count_changes([500, 321, 100, 50, 10, 5, 1], 2025))

 

많이 깔끔해졌네요...
속도도 많이 개선되었습니다. 
그리고 동전의 종류와 상관없이 작동하는
코드가 되었습니다. 

nonlocal은 함수 내 함수가 있을 때
상위 함수에서 사용하던 변수를
하위 함수에서 가져와 사용하겠다는 의미입니다. 

변수를 읽기만 할 때는
nonlocal 없어도 됩니다. 

변수의 내용을 바꿔야 하는 경우에는
명시적으로 nonlocal을 사용해야 합니다. 

개인적으로는 가독성에 도움이 되는 것 같습니다. 

 

3. 탐색의 순서를 바꿈.

위에서는 for 문으로 한 종류의 (500원짜리) 동전을 반복했는데... 

모든 종류의 코인을 반복하는 방식으로 바꿉시다. 

코드가 조금 더 깔끔해집니다.

def count_changes(money, coins):
    min_changes = money

    def recursive(total, changes):
        nonlocal min_changes
        if total == 0:
            min_changes = min(min_changes, changes)
            return
        if total < 0 or changes > min_changes:
            return
        for coin in coins:
            recursive(total - coin, changes + 1)

    recursive(money, 0)
    return min_changes


print(count_changes(2025, [500, 321, 100, 50, 10, 5, 1]))

 

4. 재귀 + 메모이제이션

하향식으로 접근해 봅니다. 

* None 대신 -1을 사용하는 것도 좋을 것 같습니다.

def count_changes(money, coins):
    memo = [None for _ in range(money + 1)]
    memo[0] = 0

    def recursive(total):
        if memo[total] is not None:
            return memo[total]
        min_changes = total
        for coin in coins:
            if total >= coin:
                result = recursive(total - coin)
                min_changes = min(min_changes, result)
        memo[total] = min_changes + 1
        return memo[total]

    return recursive(money)


print(count_changes(2025, [500, 321, 100, 50, 10, 5, 1]))

실제로 이렇게 작동하진 않지만..
간략하게..

처음 2025원어치 동전의 최소 개수를 배열에서 찾습니다.. 없죠...
없으니까 500원을 뺀 1525원어치 동전의 찾고.. 없고..
없으니까 500원을 뺀 1025원어치 동전의 찾고.. 없고..
없으니까 500원을 뺀 525원어치 동전의 찾고.. 없고..
없으니까 500원을 뺀 25원어치 동전의 찾고.. 없고..
없으니까 10원을 뺀 15원어치 동전의 찾고.. 없고..
없으니까 10원을 뺀 5원어치 동전의 찾고.. 없고..
없으니까 5원을 뺀 0원어치 동전의 찾고.. 있네요.. 0을 리턴 받고..

5원에 1개를 넣고...
15원에 2개를 넣고... 
25원에 3개를 넣고... 
525원에 4개를 넣고... 
1025원에 5개를 넣고... 
1525원에 6개를 넣고... 
2525원에 7개를 넣고... 리턴... 

실제로 어떻게 작동되는 지는
다음 코드로 확인해 봅시다. 

def count_changes(money, coins):
    memo = [None for _ in range(money + 1)]
    memo[0] = 0

    def recursive(total):
        if memo[total] is not None:
            return memo[total]
        print(total)
        min_changes = total
        for coin in coins:
            if total >= coin:
                result = recursive(total - coin)
                min_changes = min(min_changes, result)
        memo[total] = min_changes + 1
        return memo[total]

    recursive(money)
    print(memo)
    return memo[money]


print(count_changes(2025, [500, 321, 100, 50, 10, 5, 1]))

min_changes = total

최솟값을 찾을 때, 
float('inf')을 초기값으로 사용하면 편리합니다.
float 형을 int 값과 비교할 때는
시각적 불편함이 약간 느껴지지만..
파이썬은 동적 언어니까 가능합니다. 

이번 문제의 경우 1원 미만의 동전이 없다면,
1원 동전으로 전부 거스름을 마련할 때가
동전의 최대 개수가 되기 때문에..
줘야 할 잔돈 총액을 최댓값으로 두었습니다. 
보기도 안 불편하고....

1 미만의 동전도 가능한 등의 이상한 조건에선 주의해주십시오 ㅠ,.ㅠ 

 

4-1. 재귀 + lru_cache

from functools import lru_cache


def count_changes(money, coins):
    @lru_cache(maxsize=None)
    def recursive(total, changes):
        nonlocal min_changes
        if total == 0:
            min_changes = min(min_changes, changes)
            return
        if total < 0 or changes > min_changes:
            return
        for coin in coins:
            recursive(total - coin, changes + 1)

    min_changes = money
    recursive(money, 0)
    return min_changes


print(count_changes(2025, [500, 321, 100, 50, 10, 5, 1]))

 재귀함수를 캐시하면 메모이제이션과 비슷합니다.

 

5. 동적 계획법

상향식입니다. 

def count_changes(money, coins):
    memo = [None for _ in range(money + 1)]
    memo[0] = 0

    def dynamic_programming(change):
        for total in range(1, change + 1):
            min_val = total
            for coin in coins:
                if total >= coin:
                    result = memo[total - coin]
                    min_val = min(result, min_val)
            memo[total] = min_val + 1
        return memo[change]

    return dynamic_programming(money)


print(count_changes(2025, [500, 321, 100, 50, 10, 5, 1]))