프로젝트 오일러 031

문제

31번 문제

영국 화폐 액면가를 조합하는 방법의 수

사이냅소프트

동적계획법

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

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

💡"신성 로마 제국"은 신성하지도, 로마와 관련이 있지도, 제국도 아니었습니다.

문제 풀이에 앞서서 동적 계획법으로 풀 수 있는 간단한 문제를 하나 생각해보겠습니다.

13개로 이루어진 층계가 있습니다. 여러분은 이곳의 계단을 한 걸음에 하나 혹은 두 개씩 오를 수 있습니다. 이 열세 개의 계단을 오르는 방법은 총 몇 가지일까요?

이 문제를 풀기 위한 여러 가지 방법이 있을 겁니다. n개의 계단으로 오르는 방법의 수를 나타내는 표기를 P(n)이라고 하겠습니다. 우선, P(1) = 1 입니다. 1번 계단은 무조건 한 번에 한 계단을 오르는 것 밖에는 없습니다. 그리고 편의 상 P(0) = 1 이라고 하겠습니다. 왜냐하면 P(2) 때문입니다.

두 개의 계단을 오르는 방법은 1) 한 번에 한 계단 씩 두 걸음에 오르거나, 2) 한 번에 두 계단을 오르는 두 가지 방법이 있습니다. 이 상황을 잘 생각해보면,

• 두 계단 아래까지 오는 모든 방법들의 끝에서 한 걸음에 두 계단을 성큼 올라오는 방법과
• 한 계단 아래까지 오는 모든 방법들의 끝에서 한 계단을 더 올라오는 방법이 있습니다.

따라서 P(2) = P(1) + P(0) 입니다. 그리고 이는, 2 뿐만 아니라 임의의 n에 대해서도 동일합니다.

P(n) = P(n - 1) + P(n - 2)

어? 이거 어디선 가 본 거 아닙니까? 피보나치 수열을 만드는 점화식과 똑같아요!

특정 금액을 만드는 방법의 수

만약 1펜스와 2펜스 동전만으로 2파운드를 만드는 방법의 수를 구하라는 문제라면 위의 문제와 똑같습니다. 근데 동전의 종류가 좀 많죠. 동전이 1, 2, 5 펜스가 있다고 가정하고 20펜스를 만들어보겠습니다.

n 펜스를 만들 수 있는 방법의 수를 P(n) 이라고 한다면, 동일한 방법으로 점화식을 구할 수 있습니다.

P(n) = P(n - 5) + P(n - 2) + P(n - 1) (단 n < 0 이면 P(n) = 0, P(0) = 1)

그런데 이 점화식에는 문제가 있습니다. 계단을 오르는 문제에서는 3단을 오르기 위해서는 (1, 1, 1), (1, 2), (2, 1) 로 순서가 다르면 다른 방법으로 봅니다. 그런데 3펜스를 만드는 방법에서는 1 + 2 와 2 + 1은 같은 것으로 봐야 합니다.

동전을 '조합'하여 금액을 만드는 것이기 때문에, 같은 조합 다른 순서의 중복을 제거하는 알고리듬이 필요합니다. 이를 구현하기 위해서는 점화식에 '현재 사용할 동전'에 대한 정보가 들어가야 합니다. 즉 사용할 동전을 크기 순대로 정렬해서, 작은 것부터 먼저 사용하여 방법의 가짓수를 구하고, 이미 사용한 것보다 크거나 같은 동전만 사용하도록 규칙을 정하면 중복을 피할 수 있습니다.

따라서 이 점화식에는 사용할 사용할 동전이 두 번째 인자로 추가되어야 합니다.

| P(n, coin) = P(n, next_coin) + P(n - coin, coin)
| P(0, any) = 1, p(any, o) = 0

식이 복잡해졌지만, 주어진 액면가의 동전을 사용하지 않는 경우와 사용하는 경우를 합치는 것으로 이해하면 됩니다. 이 과정을 코드로 만들면 아래와 같습니다. (피보나치 수열 점화식의 변형이므로 더욱 반복계산이 많고 느립니다. 그래서 메모이제이션한다고 생각해야 합니다.)

coins = (1, 2, 5, 10, 20, 50, 100, 200)
cache = {}


def p(target, ci=0):
  """ target=금액, ci = 동전의 인덱스 """
  # 캐싱된 결과
  key = (target, ci)
  if key in cache:
    return cache[key]
    
  # 기저 사례
  if target == 0:
    return 1
    
  # 실질적으로 만들 수 없는 금액이나 조합은 0으로
  if target < 0 or ci > len(coins):
    return 0

  # ci동전을 사용하지 않을 때 + ci 동전을 사용할 때.
  res = p(target, ci + 1) + p(target - coin[ci], ci)
  cacke[key] = res
  return res

print(p(200))
  

동적계획법으로 가속하기

메모이제이션을 사용하는 기법으로도 충분히 풀 수 있습니다만, 이런 유형의 문제는 다음과 같이 더 간단해보이는 풀이를 사용할 수 있습니다. 같은 원리인데 구현만 다른 것으로 이해하면 됩니다.

def f(n):
  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]

같은 알고리듬이지만, 이 구현을 보면 너무 간단해서 더 어려워보입니다.

동적계획법은 복잡해보이는 문제를 더 작은 하위 문제들로 나누고 이를 해결하는 알고리즘 설계 기법입니다. 이 때 각 하위 문제의 결과는 저장하여 재사용합니다. 메모이제이션은 동적계획법의 한 가지 방법입니다. 동적계획법을 적용하여 최적화할 수 있는 문제는 다양한데, 그럼에도 큰 문제의 최적해가 작은 문제의 최적해로부터 구성될 수 있어야하며, 중복되는 동일한 작은 문제들이 나타나야 합니다. 일반적으로 동적계획법은 최단 경로문제나 최장 증가 부분 수열, 문자열의 편집거리 계산하기 등의 문제에 적용하는 것이 대표적인 활용 사례입니다.