๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Coin Change | LeetCode 809 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

     

    ๐Ÿค” ๋ฌธ์ œ : Coin Change | LeetCode 780

    ๋ฌธ์ œ: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/809/

    ๋™์ „์„ ์กฐํ•ฉํ•˜์—ฌ ๊ฐ€์žฅ ์ ์€ ๋™์ „ ์กฐํ•ฉ์œผ๋กœ ์ฃผ์–ด์ง„ ๊ธˆ์•ก์„ ๋งŒ๋“œ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 

    ์ „ํ˜•์ ์ธ Dynamic Programming ๋ฌธ์ œ๋„ค์š”.

     

    Dynamic Programming

    1. ํฐ ๋ฌธ์ œ๋Š” ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ‘ผ๋‹ค

    2. ์ž‘์€๋ฌธ์ œ์—์„œ ํ‘ผ ์ •๋‹ต์€ ๊ธฐ์–ตํ•ด๋‘์—ˆ๋‹ค๊ฐ€ ๋™์ผํ•œ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜ค๋ฉด ๊ทธ๋Œ€๋กœ ํ™œ์šฉํ•œ๋‹ค.

     

     

    ๐Ÿ’ก ํ’€์ด

    1. Top Down 

    amount์—์„œ ๋™์ „๋งŒํผ์”ฉ ๊นŽ์•„๋‚ด๋ ค๊ฐ€๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

    dp()๋ผ๋Š” ํ•จ์ˆ˜๋ฅผ recursiveํ•˜๊ฒŒ ํ˜ธ์ถœํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. 

    from typing import List
    from functools import lru_cache
    import math
    
    class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            if not coins: return -1
            INF = math.inf
            @lru_cache(None)
            def dp(n):
                if n < 0: return -1
                if n == 0: return 0
                ans = INF
                for c in coins:
                    if dp(n-c) >= 0:
                        ans = min(ans, dp(n-c)+1)
                return ans
            return dp(amount) if dp(amount) < INF else -1

     

    - @lru_cache

    python์—์„œ๋Š” memoization๋Œ€์‹  cache๋ฅผ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. 

    @lru_cache ๋ฐ์ฝ”๋ ˆ์ดํ„ฐ๋ฅผ ํ™œ์šฉํ•˜๋ฉด ํ•ด๋‹น ํ•จ์ˆ˜์— ๋Œ€ํ•œ ๊ฒฐ๊ณผ๊ฐ’์„ ์บ์‹ฑ๋ฉ๋‹ˆ๋‹ค. 

    ์ฆ‰, ํ•œ ๋ฒˆ ๊ณ„์‚ฐํ•œ ๊ฐ’์€ ๋‹ค์‹œ ๊ณ„์‚ฐํ•˜์ง€ ์•Š๊ณ  ์บ์‹ฑ๋œ ๊ฐ’์„ ๊ทธ๋ƒฅ ๊ฐ€์ ธ์˜ต๋‹ˆ๋‹ค. 

     

    - ์˜ˆ์‹œ

    Input: coins = [3, 5], amount = 8

    ์ด ๊ฒฝ์šฐ์— dp๊ฐ€ ์–ด๋–ป๊ฒŒ ํ˜ธ์ถœ๋˜๋Š”์ง€ ์ƒ๊ฐํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

     

    dp(8) : min(1, 1)+1 = 2

    - 3, 5๋ฅผ ๋บ€ ๊ฐ’์— ๋Œ€ํ•ด ๊ฐ๊ฐ dp ํ˜ธ์ถœ

    - dp(5) : min(0, INF) +1 = 1

       - 3, 5๋ฅผ ๋บ€ ๊ฐ’์— ๋Œ€ํ•ด ๊ฐ๊ฐ dp ํ˜ธ์ถœ  -> 0์ด์ƒ์ธ ๊ฐ’ ์ค‘ min๊ฐ’ 

       - 1) dp(5-3) : dp(2) = INF

            - 3, 5๋ฅผ ๋บ€ ๊ฐ’์— ๋Œ€ํ•ด ๊ฐ๊ฐ dp ํ˜ธ์ถœ -> 0์ด์ƒ์ธ ๊ฐ’ ์ค‘ min๊ฐ’ 

            - dp(-1) = -1

            - dp(-3) = -1

        -2) dp(5-5) : dp(0) = 0

    - dp(3) : 0 + 1 = 1

       - 3, 5๋ฅผ ๋บ€ ๊ฐ’์— ๋Œ€ํ•ด ๊ฐ๊ฐ dp ํ˜ธ์ถœ  -> 0์ด์ƒ์ธ ๊ฐ’ ์ค‘ min๊ฐ’ 

       - 1) dp(3-3) : dp(0) = 0

        -2) dp(3-5) : dp(-2) = -1

     

     

    2. Bottom Up

    0์—์„œ๋ถ€ํ„ฐ amount๊นŒ์ง€ ์˜ฌ๋ผ๊ฐ€๋ฉฐ ๋ช‡๊ฐœ์˜ ๋™์ „์ด ํ•„์š”ํ•œ์ง€ ๊ตฌํ•˜๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค. 

    class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            INF = math.inf
            dp = [0]+[-1]*amount
            for i in range(min(coins), amount+1):
                # print(i, [i-c for c in coins if i-c >= 0 and dp[i-c] >= 0])
                dp[i] = min((dp[i-c] for c in coins if i-c >= 0 and dp[i-c] >= 0), default=-2)+1
            return dp[amount]

     

    - ์˜ˆ์‹œ

    Input: coins = [3, 5], amount = 8

    ์ด ๊ฒฝ์šฐ์— Bottom-up ๋ฐฉ์‹์œผ๋กœ๋Š” dp ๋ฐฐ์—ด์ด ์–ด๋–ป๊ฒŒ ์ฑ„์›Œ์งˆ๊นŒ์š”?

    ๋ฐ˜์‘ํ˜•