๐ ๋ชฉ์ฐจ
๐ค ๋ฌธ์ : Coin Change | LeetCode 780
๋์ ์ ์กฐํฉํ์ฌ ๊ฐ์ฅ ์ ์ ๋์ ์กฐํฉ์ผ๋ก ์ฃผ์ด์ง ๊ธ์ก์ ๋ง๋๋ ๋ฌธ์ ์ ๋๋ค.
์ ํ์ ์ธ 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 ๋ฐฐ์ด์ด ์ด๋ป๊ฒ ์ฑ์์ง๊น์?
'์๊ณ ๋ฆฌ์ฆ > LEETCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Search a 2D Matrix II | LeetCode 806 | Python3 ๐ (0) | 2022.03.14 |
---|---|
Search in Rotated Sorted Array | LeetCode 804 | Python3 ๐ (0) | 2022.03.13 |
Merge Intervals | LeetCode 803 | Python3 ๐ (0) | 2022.03.10 |
Search for a Range | LeetCode 802 | Python3 ๐ (0) | 2022.03.09 |
Sort Colors | LeetCode 798 | Python3 ๐ (0) | 2022.03.06 |