프로젝트 오일러 031

동적계획법

개인적으로 프로젝트 오일러의 초반 문제중에서 제일 좋아하는 문제입니다. 이 문제를 통해서 ‘동적계획법’이라는 것을 처음 알게 되었는데요. 최초로 작성했던 코드에 비교해서 동적계획법으로 작성한 코드가 비교도 안될 정도로 엄청나게 성능이 좋았던 건 물론이요, 동적 계획법으로 문제를 접근하면 중복된 경우를 세는 등의 문제도 아주 명확하게 피할 수 있습니다.

동적계획법은 ‘dynamic programming’이라는 이름과 달리 동적이지도, 뭔가를 계획하는 방법도 아닙니다. ‘신성 로마 제국’하고도 비슷한 느낌인데요, 단순히 이 알고리듬이 고안되던 시절에는 ‘programming’이라는 말이 ‘수학적인 최적화 방법’이라는 의미로 사용되었기 때문입니다. 그리고 ‘dynamic’은 시간에 따라 변화하는 값에 대한 최적화를 강조하는 맥락에서 사용되었다고 하네요.

계단 문제와의 차이점

이 문제와 비슷하면서도 다른 문제를 먼저 하나 살펴보겠습니다.

“13개의 층계로 이루어진 계단이 있습니다. 우리는 이 계단을 한 걸음에 한 칸 혹은 두 칸을 오를 수 있습니다. 이 계단을 오르는 모든 방법의 수는 몇 가지 인가요?”

간단해 보이지만 이 문제의 답을 일일이 세려고 하면 생각보다 힘들다는 것을 금새 깨닫게 됩니다. 따라서 이런 접근이 필요할 수 있습니다. 계산 중간의 특정 위치에서 할 수 있는 액션은 한 계단을 오르거나 두 계단을 오르는 것입니다. 거꾸로 13번째 계단에 올라왔을 때에는 이 직전에 12번째 계단에 있었거나, 11번째 계단에 있었거나 둘 중 하나입니다. 따라서 13개 계단을 오르는 경우의 수는 다음 경우의 수를 합친 것과 같습니다.

1. 11번째 계단에 오르는 모든 경우의 수에 대해 각 경우에서 2계단 오름
2. 12전째 계단에 오르는 모든 경우의 수에 대해 각 경우에서 1계단 오름

n번째 계단에 오르는 모든 경우의 수를 S(n)이라 하면, 다음의 점화식을 정의할 수 있습니다.

1. S(n) = S(n - 1) + S(n - 2)
2. S(1) = 1
3. S(0) = 1 (계단을 오르지 않는 것은 움직이지 않는 것으로 하나의 방법으로 봅니다.)

이렇게 하면 S(n)을 구할 수 있습니다. 가만, 이것은 피보나치 수열을 구하는 식과 같지 않나요?

그렇다면 동전문제도 이렇게 풀 수 있을까요? 예를 들어 200펜스를 만드는 방법을 S(200)을 각 동전의 액면가 차이만큼 뺀 금액을 만드는 방법의 경우의 수의 합계로 보는 것입니다. 이 방법은 언뜻 잘 작동할 것 같지만, 동전 문제와 계단 문제는 차이가 있습니다.

계단문제에서 S(3)은 (1, 1, 1), (1, 2), (2, 1)의 세 가지 방법이고, (1, 2)와 (2, 1)은 서로 다른, ‘순서가 중요한(ordered)’ 조합입니다. 이에 비해 동전을 조합하는 방법은 동전의 순서가 없는(unordered) 방법입니다. 2펜스+1펜스와 1펜스+2펜스는 중복입니다.

중복을 제외하는 방법

어떻게 하면 중복을 피해서 계산할 수 있을까요? 다시 계단 문제로 돌아와서 생각해봅시다. 만약 계단 문제에서도 (2, 1), (1, 2)를 같은 것으로 보고 중복되지 않게하기 위해서는 다른 조건이 필요할 수 있습니다. 일반적으로 중복을 피하는 방법은 선택할 수 있는 보폭의 순서를 제한하는 것입니다. 즉, 2칸을 오르는 이후에는 한 칸씩 오르는 방법을 사용할 수 없게 하는 것입니다.

따라서 각 계산은 n번째 관한 항이 계산일뿐만 아니라 k번째 걸음 수 (혹은 액면가)도 같이 고려되어야 합니다.

1. 0번째 칸에 도달하는 방법은 1가지입니다.
2. 음수번째 칸에 도달하는 방법은 0가지입니다.
3. S(n) = S(n, 1) + S(n, 2)입니다. 이 때
4. S(n, 1) = S(n - 1, 1), S(n, 2) = S(n - 2, 2)입니다.

이 때 1, 2라고 한 부분은 실제로는 k번째 동전의 액면가에 해당합니다. 그리고 이 계산은 아주 많은 반복 계산이 일어나므로 이전에 계산한 결과를 캐싱해두면 성능상 잇점이 있습니다. 이것을 일반화하여 정리하면 다음과 같습니다.

steps = (1, 2)
cache: dict[tuple[int, int], int] = {}

def S(n:int, idx:int=0) -> int:
    # 캐시된 결과가 있으면 캐시 사용 
    key = (n, idx)
    if key in cache:
        return cache[key]
        
    # 0번째 항은 항상 1
    if n == 0:
        return 1
        
    # 사용할 수 없는 항이나 인덱스는 무효
    if n < 0 or idx >= len(steps):
        return 0
        
    # 현재 사용할 수 있는 인덱스의 걸음 혹은 동전액면가를 사용한 방법과, 그 다음 걸음(액면가)를 사용한 방법을 모두 더함
    result = S(n - steps[idx], idx) + S(n, idx + 1)
    cache[key] = result
    return result

print(S(13))

이 방법은 동전 문제의 해법과 완전히 동일합니다. steps의 값을 동전의 액면가로 변경해주면 그대로 사용할 수 있습니다.

steps = (1, 2, 5, 10, 20, 50, 100, 200)
cache: dict[tuple[int, int], int] = {}

def S(n:int, idx:int=0) -> int:
    # 캐시된 결과가 있으면 캐시 사용 
    key = (n, idx)
    if key in cache:
        return cache[key]
        
    # 0번째 항은 항상 1
    if n == 0:
        return 1
        
    # 사용할 수 없는 항이나 인덱스는 무효
    if n < 0 or idx >= len(steps):
        return 0
        
    # 현재 사용할 수 있는 인덱스의 걸음 혹은 동전액면가를 사용한 방법과, 그 다음 걸음(액면가)를 사용한 방법을 모두 더함
    result = S(n - steps[idx], idx) + S(n, idx + 1)
    cache[key] = result
    return result
    
print(S(200))

다른 방법

명시적으로 캐시를 이용한 이런 방법도 있지만, 아래와 같은 방법으로도 해결할 수 있습니다. k번째 액면가의 동전만 사용하여 각 금액을 구성하는 방법을 모두 계산해두고, 다시 k + 1번째 액면가의 동전을 사용하는 방법을 업데이트해 나가는 것입니다.

• 액면가 1인 동전만 사용하는 경우 S(30, 1)은 S(29, 1)과 같습니다.
• 액면가 2인 동전도 사용하게되면 S(30, 2)는 S(30, 1) + S(28, 2)와 같습니다.
• 액면가 5인 동전을 사용하면 S(30, 5)는 S(30, 2) + S(25, 5)와 같습니다.
• 이 때 30보다 작은 금액에 대해서는 각 경우에 대해서는 각 시점 사이에 추가로 계산했다는 전제가 필요합니다.

따라서 액면가를 기준으로 각 금액을 구성하는 방법을 계속 업데이트하는 방식으로 배열을 사용하여 금액을 구성하는 방법을 다음과 같이 계산할 수 있습니다. 이렇게하면 이상하리만치 코드가 단순하고, 앞서 복잡하고 긴 설명과는 별로 관련이 없어 보이기까지 합니다.

def f(n):
  coins = (1, 2, 5, 10, 20, 50, 100, 200)
  ways = [0] * (n + 1)
  ways[0] = 1
  for coin in coins:
    for i in range(coin, n + 1):
      ways[i] += ways[i - coin]
  ways[-1]