Greedy vs DP

코인 문제

경우 1. 정해진 금액을 가장 적은 수의 코인(동전)으로 구성하는 문제를 풀 때(단 각 동전 액면은 무한히 사용 가능), 1, 2, 5, 10, 20, 50, 100, 200 cents 로 되어 있는 유로화 코인이나 1, 5, 10, 50, 100, 500으로 된 원화 동전은 가장 큰 액면부터 차례로 채우면 최적해를 구할 수 있다. 두 경우 모두 뒤의 액면 중에는 이전 액면의 배수가 존재하므로 어느 액면이나 그 전단계의 동전을 통해 구할 수 있고, 이런 경우는 가장 큰 코인부터 답에 포함하게 된다면, 더 적은 액면으로 구성한 뒤 더 큰 액면으로 바꾼 결과와 다름이 없어 최적해가 되는 것이다. 예를 들어 1520원을 구성하고 싶으면 500 * 3 + 10 * 2 이렇게 5개 동전이 최적해이다.

차이가 있다면 유로화는 건너서 배수가 존재하는 경우가 있는 반면 (1 -> 5 -> 10, 2 -> 10 등) 원화는 직전 액면의 배수가 바로 다음 액면이 된다. 그래서 원화는 더 적은 동전 가지수로도 그리디 해를 보장하도록 훌륭하게 설계된 것이라고 할 수 있다.

경우 2. 그러나 만일 액면이 1, 3, 4 처럼 되어 있는 경우 6을 구성하고 싶으면 그리디로 구하면 4 * 1 + 1 * 2 = 3개 이지만, 3 * 2 = 2개의 최적해가 존재하므로 그리디 알고리즘은 최적해를 보장하지 않는다.

이 경우는 완전탐색(또는 brute force)나 DP로 풀 수 있다. 두 알고리즘 모두, 모든 경우를 다 탐색하는 것은 동일하지만 후자는 memoization을 통해 각 경우에 대한 계산이 1번씩만 행해지도록 하는 반면, 전자는 매번 이를 다시 계산해야 하므로 지수(exponential) 시간복잡도를 갖게 된다. 그러면, 지금부터 경우 2에 대해서 최적해를 구하는 과정을 살펴보자.

완전탐색

재귀를 활용하여 완전탐색한다. 먼저 함수를 다음과 같이 정의한다.

solve(x) : 금액 x를 구성하는 최적의 코인 수를 구함

그렇다면 다음과 같이 해를 구할 수 있다.

coins = {1, 3, 4}

solve(0) = 0
solve(1) = 1
solve(2) = 2
solve(3) = 1
solve(4) = 1
solve(5) = 2
solve(6) = 2
solve(7) = 2
...

만일 합계 10을 구하고자 한다면 어떻게 위의 정보를 활용해야 할까. 우선, 그리디는 최적해를 보장하지 않는다고 했으므로 모든 경우를 따져보는 것이 바람직하지만, 주의깊게 정보를 활용하는 것이 현명하다. 즉, 10을 만들기 위해 모든 coin을 고르는 경우를 생각해 보아야 한다. 그러나 각 경우 모두 1개를 고르는 것부터 우리가 경우의 수로 생각할 수 있다. 처음 문제를 풀기 시작한 지점에서 세 경우의 갈림길로 간 결과를 놓고 최소의 갯수를 고르는 것이므로, 다음 식으로 생각하자.

solve(10) = min(1 + solve(10-1), 1 + solve(10-3), 1 + solve(10-4))

그러면 원래의 문제인 합계 10 구성하기는 세 가지 부분문제를 고민하여 비교하는 것으로 바뀌었다. 다시 부분문제를 같은 방식으로 푼다면 결국 재귀함수를 풀게 된다. 다만, 부분문제가 다시 더 작은 부분문제들을 탐색하는 동안 이미 기존에 풀었던 문제를 다시 풀게 될 수 있으므로 이는 비효율적이다. 코드를 적어본다.

def solve(x, coins={1, 3, 4}):
    if x < 0: return float('inf')
    if x == 0: return 0
    best = float('inf')   # to get the min of the result of subproblems
    for c in coins:
        best = min(best, solve(x - c) + 1)
    return best

# 주석을 단 부분은 각 (부분)문제에 해당하는 함수에서 최소값을 구하기 위한 것으로, 어떤 coins 종류가 나오더라도 풀 수 있도록 하기 위해(늘 코인의 종류가 우리 경우 2 에서 처럼 3개는 아니므로) 많이 쓰이는 관용구라고 할 수 있겠다. 일단 최대값을 정해놓고 각 코인 액면을 1개씩 고르면서 얻어진 부분문제에 또 다시 재귀를 보내는 것이다. 이 함수의 형태는 재귀 과정에서 동일하게 적용되므로 여기에 base case도 지정해야 된다. 만일 부분문제가 음수의 합을 구하는 것이라고 한다면, coins에는 양수의 액면만이 존재할 것이므로 문제를 풀 수가 없기에 풀 수 없다는 뜻으로 무한대를 돌려준다. 이 함수를 받아 실행할 다른 함수의 요구에 따라서 다른 것을 돌려줄 수도 있다. 하지만 -1 등을 돌려줄때는 재귀호출을 한 함수에서 겨우 1이 더해지게 되어 올바른 값처럼 처리가 될 수 있음에 유의하자. 만일 x가 0이 된다면, 합 0을 구성하는 최소의 동전 갯수는 0이므로 0을 돌려준다.

DP (recursion, top-down)

그런데 만일 첫번째 표와 같이, 계산결과를 적어놓은 것이 있다면 어떨까. 위의 재귀함수도 그저 기존에 계산된 것이 있는 경우 그것을 갖다쓰고 그렇지 않다면 새로 계산해서 나중에 갖다쓸 수 있게 저장한 뒤 계산된 결과를 돌려주면 된다. 이렇듯, 위 문제를 메모를 이용해 푸는 방법이 DP이다. LeetCode의 문제내용에 맞게 코드를 일부 변형하였다. 각 함수의 결과값을 lru_cache 모듈을 이용해 저장하면 더 효과적으로 풀 수 있다.

문제: https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

from functools import lru_cache
def coinChange(coins: List[int], amount: int) -> int:
    if amount < 1: return 0
    @lru_cache(None)
    def dp(x):
        if x < 0: return -1
        if x == 0: return 0
        minimum = float('inf')
        for c in coins:
            res = dp(x - c)
            if 0 <= res < minimum:
                minimum = 1 + res
        if minimum == float('inf'):
            return -1
        return minimum
    return dp(amount)

DP (bottom-up)

위의 과정은 결국 표에 값을 저장하는 것과 동일하다. 그러므로 맨 처음 표를 구성했던 과정을 유사하게 모사하면 상향식 DP를 구성할 수 있다. 표를 다시 가져와 보겠다.

coins = {1, 3, 4}

solve(0) = 0
solve(1) = 1
solve(2) = 2
solve(3) = 1
solve(4) = 1
solve(5) = 2
solve(6) = 2
solve(7) = 2
...

solve(10) = min(1 + solve(10-1), 1 + solve(10-3), 1 + solve(10-4))

이 값을 어떻게 계산하는 것이 효율적이었을까. 10을 계산하기 위해 스택을 만들어 재귀를 보내는 것 보다, 작은 수부터 계산해서 목표한 값 10이 될 때 까지 작업을 하면 제일 좋을 것이다. 즉, 위 박스의 맨 아랫 식을 계산할 때 10부터 시작하는 것이 아니라, 0부터 계속 올라가면서 작업하는 것이다.

즉, solve(0) = 0 임은 정의에 의해 당연하다. 그 다음, solve(1) 은 min(1 + solve(1-1), 1 + solve(1-3), 1 + solve(1-4)) = min(1 + solve(0), 1 + solve(-2), 1 + solve(-3)) = min(1 + 0, 1 + inf, 1 + inf) = 1 이 된다. 이 과정을 계속 solve(2), solve(3) ... solve(10) 에 대해 하고 solve(10)을 돌려준다.

value = {}
def solve(n):
    value[0] = 0
    for x in range(1, n + 1):
        value[x] = float('inf')
        for c in coins:
            if x-c in value:
                value[x] = min(value[x], value[x - c] + 1)
    return value[n]

>>> coins = {1,3,4}
>>> print(solve(10))
3