[Algorithm] 동전 교환 문제(Coin Change Problem)로 공부하는 동적 프로그래밍(Dynamic Programming)

Dynamic Programming(DP)의 장점은 중복되는 부분 문제(Overlapping Subproblems)와 최적 부분 구조(Optimal Substructure)를 가지는 문제를 효율적으로 해결할 수 있다.

 

오늘은 동전 교환 문제에 대해 풀어보고 설명해보자.

 

동전 교환 문제는 DP의 대표적인 최적화 문제이다. 주어진 금액을 특정 동전 단위로 만들기 위해 필요한 최소 동전의 개수를 구하는 것이 목표이다.

 

 

 

풀이를 먼저 확인해보자.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
 
 
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
 
    return dp[amount] if dp[amount] != float('inf') else -1
 
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # Output: 3

 

 

나는 액면가가 11이 되는데, 최소한의 동전 개수를 찾는게 목표이다. 

그러기 위해서 dp 배열을 만들어서 금액 11이 되기 전까지의 각 금액에 도달하기까지의 최소 동전 개수를 저장하는 배열을 설계했다.

 

dp배열은 금액 0부터 amount(11)까지의 값까지의 값을 저장하며, 초기값은 아직 계산되지 않은 상태를 표현하기 위해 무한대 값( float('inf') ) 으로 설정했다.

또한, dp[0] = 0으로 초기화한 이유는 금액이 0일 때 필요한 동전 개수는 0개이기 때문이다.

 

6라인은 금액 1부터 11까지의를 순차적으로 계산하기 위한 for문이다.

7라인은 현재 사용 가능한 코인(denomination)을 하나씩 대입하면서 최소값을 찾는 과정이다.

점화식 dp[i] = min(dp[i], dp[i - coin] + 1)은 현재 코인을 사용했을 때의 동전 개수와 이미 저장된 최소값을 비교해 더 작은 값을 저장하는 역할을 한다.

 

모든 for문이 실행되면 dp배열에는 0부터 11까지의 각 금액을 만들기 위한 최소 동전 개수가 저장된다.

마지막으로 dp[amount] ( dp[11] )에 값이 존재하면 해당 금액을 만들기 위해 필요한 최소 동전 개수를 반환하고, 만약 값이 여전히 무한대라면 해당 금액을 만들 수 없다는 의미이므로 -1을 반환한다.