View in English →

Code › algorithm-study

LeetCode 322 - Coin Change

남은 금액별 최소 동전 수를 저장하는 DFS memoization Python 풀이

algorithmleetcodedynamic-programmingdfsmemoizationrecursionpythonlearning

동전의 종류와 목표 금액이 주어졌을 때, 목표 금액을 만드는 데 필요한 최소 동전 수를 구하는 Medium 문제다. 남은 금액을 재귀적으로 줄여가며 탐색하되, 같은 금액에서 시작하는 계산을 반복하지 않도록 결과를 memo에 저장했다.

문제 링크 & 설명

  • 문제 링크: 322. Coin Change
  • 요약: 정수 배열 coins와 정수 amount가 주어졌을 때, 동전으로 amount를 만드는 데 필요한 최소 개수를 반환한다. 금액을 만들 수 없다면 -1을 반환하며, 각 동전은 여러 번 사용할 수 있다.

예를 들어 coins가 [1, 2, 5]이고 amount가 11이라면 5 + 5 + 1로 만들 수 있으므로 답은 3이다. 가능한 조합 하나를 찾는 것으로 끝나는 문제가 아니라, 모든 가능한 선택 중 동전 수가 가장 작은 결과를 골라야 한다.

접근 방법

DFS의 상태는 현재 만들어야 할 남은 금액 remain이다. 각 단계에서 사용할 수 있는 동전을 하나씩 빼고, 줄어든 금액을 만드는 데 필요한 최소 동전 수를 재귀적으로 구한다.

for coin in coins:
    min_result = min(
        min_result,
        self.dfs(coins, memo, remain - coin),
    )

remain이 0이면 목표 금액을 정확히 만든 것이므로 필요한 동전 수는 0이다. 반대로 remain이 음수가 되면 현재 선택으로는 금액을 정확히 만들 수 없기 때문에 무한대를 반환한다.

if remain == 0:
    return 0
if remain < 0:
    return float('inf')

재귀 호출에서 유효한 결과를 찾았다면 현재 단계에서 선택한 동전 하나를 더해야 한다. 계산한 값은 remain을 key로 memo에 저장하고, 같은 금액이 다시 나오면 재귀 탐색 없이 저장된 결과를 반환한다.

if remain in memo:
    return memo[remain]

memo[remain] = (
    min_result
    if min_result == float('inf')
    else min_result + 1
)

coins가 [1, 2, 5]일 때 remain 6은 11에서 5를 뺀 경로에서도 나오고, 8에서 2를 뺀 경로에서도 나올 수 있다. memoization이 없으면 remain 6 아래의 계산을 경로마다 다시 수행하지만, 결과를 저장하면 각 남은 금액은 한 번만 계산한다.

트러블 슈팅

만들 수 없는 금액을 재귀 호출 내부에서 바로 -1로 반환하면 최소값을 고르는 과정에서 문제가 생긴다. -1은 정상적인 동전 개수보다 작기 때문에 실패한 경로가 오히려 최솟값으로 선택될 수 있다.

그래서 재귀 내부에서는 만들 수 없는 상태를 무한대로 표현했다. min 연산에서는 무한대가 선택되지 않고, 모든 경로가 무한대일 때만 현재 remain도 만들 수 없는 상태로 남는다. LeetCode가 요구하는 -1로의 변환은 가장 바깥 coinChange 함수에서 한 번만 처리했다.

result = self.dfs(coins, {}, amount)
return result if result != float('inf') else -1

풀이 코드의 기존 주석에는 시간 복잡도를 지수 시간으로 적었지만, 이는 memoization을 적용하지 않은 재귀 탐색에 해당한다. 이 풀이에서는 같은 remain을 다시 계산하지 않으므로 남은 금액의 상태 수와 동전 종류 수를 기준으로 복잡도를 계산해야 한다.

복잡도 분석

  • 시간 복잡도: O(amount × k)
    • remain은 0부터 amount까지의 범위에서 memoization되고, 각 상태에서 k개의 동전을 확인한다. k는 coins의 길이다.
  • 공간 복잡도: O(amount)
    • 남은 금액별 결과를 memo에 저장하고, 재귀 호출 스택도 최악의 경우 amount에 비례해 깊어질 수 있다.

구현 코드

from typing import Dict, List

class Solution:
    def dfs(
        self,
        coins: List[int],
        memo: Dict[int, int],
        remain: int,
    ) -> int:
        if remain == 0:
            return 0
        if remain < 0:
            return float('inf')
        if remain in memo:
            return memo[remain]

        min_result = float('inf')

        for coin in coins:
            min_result = min(
                min_result,
                self.dfs(coins, memo, remain - coin),
            )

        memo[remain] = (
            min_result
            if min_result == float('inf')
            else min_result + 1
        )
        return memo[remain]

    def coinChange(self, coins: List[int], amount: int) -> int:
        result = self.dfs(coins, {}, amount)
        return result if result != float('inf') else -1

요약 및 회고

이 문제에서 반복되는 상태는 지금까지 선택한 동전 목록이 아니라 남은 금액이다. 같은 remain에 도달했다면 그 아래에서 필요한 최소 동전 수는 이전 경로와 관계없이 같기 때문에, remain을 기준으로 결과를 저장할 수 있다.

DFS만 사용하면 같은 금액을 여러 경로에서 반복 계산하지만, memoization을 추가하면 amount 범위의 각 상태를 한 번씩 계산한다. 재귀 구조는 그대로 두면서 지수적으로 늘어나던 중복 탐색을 제거한 top-down dynamic programming 풀이였다.