오일러 프로젝트 31번 문제의 풀이는 해당 포스트에서 보면 허무하리만치 짧고 간단하며, 어찌보면 굉장히 이해하기 힘든 식으로 코드가 짜여져 있다. 게다가 재귀라든지 여러가지 그외 방법으로 푸는 것 보다 속도도 엄청 빠르다. (당연할 것이 재귀 호출 같은 것은 전혀 생각하지 않고 그저 정수 배열의 일부 항끼리 서로 더해나가는 2중 루프가 전부이다.) 이런 괴상한 풀이는 어떻게 나오게 되었으며, 어떤 식으로 알고리듬을 짠 것일까?
순진한 접근
가장 순진한 접근방법을 생각해보자. 동전의 액면가가 
에 대해서
짜리 동전을 쓰는 경우를 생각해본다. 이는
의 각 케이스에 대해서
- 다른 동전들에 대해서도 마찬가지 규칙이 적용될 수 있으므로
를 구한다. 그리고 이 때 중복되는 조합의 케이스가 있다 이들을 제거하고 개수를 세면
- 이 때, 동전 액면가의 차액 만큼의 조합들도 같은 방식으로 풀 수 있다.
결국 n으로부터 시작해서 그 이하의 동전의 차액으로 구성할 수 있는 금액들을 만드는 조합들을 모두 구하고, 중복을 제거한 뒤에 세어야 한다는 이야기다. 예를 들어 2, 3원 동전을 쓸 수 있다고 가정하면 7원을 만드는 지점에서 (2 + 2 + 3), (2 + 3 + 2), (3 + 2 + 2) 가 각각 나올 수 있고, 이 들은 모두 중복되는 케이스가 된다. 중복을 제거할 케이스들을 모두 구해야 하고, 비교를 위해서는 케이스의 개수를 세는 것이 아닌 모든 조합을 구해서 비교해야 한다. 그리고 특정 금액에 대한 조합은 반복적으로 계산해야 할 수 밖에 없다.
구현
구현자체의 아이디어는 재귀를 통한다. 위에서 이야기한 아이디어를 그대로 구현했다. 모든 동전 조합은 set에 넣어서 중복을 제거했고, 이를 위해서 리스트와 튜플 사이를 변환한다.
def coin_combs(n, coins):
"""coins에 포함된 동전으로 n원을 만드는 모든 조합을 구한다"""
## 결과는 중복을 제거하기 위해서 set을 사용한다.
result = set()
## 실제로 사용가능한 동전은 n원 이하의 액면가만 사용할 수 있다.
available_coins = [coin for coin in coins if n >= coin]
## 각 동전에 대해서
for coin in available_coins:
## n 보다 작은 액면가라면 차액만큼을 만드는 경우를 뽑아내고,
if n > coin:
temp_result = coin_combs(n-coin, available_coins)
## 만들어진 임시결과의 모든 조합의 끝에 현재 동전을 하나씩 추가한다.
## 그리고, 만든 리스트는 set에 들어갈 수 없으므로 정렬하여 튜플로 변환한다.
temp_result = {tuple(sorted(list(x) + [coin])) for x in temp_result}
else:
## 액면가가 n과 같다면, 1가지 가지 밖에 없다.
temp_result = { (coin, ) }
## 이상의 임시 결과를 현재 결과에 추가한다.
result = result.union(temp_result)
return result그리고 예상은 했겠지만, 시간 복잡도는 지수적이기 때문에, 1, 2, 5, 10 원으로 30원을 만드는데는 약 55초 가량이 걸렸다. 1, 2, 5, 10, 50, 100 으로 200을 만드는데는 엄청난 인내심이 필요할 것이다.
메모이제이션
여기서 문제가 되는 것은 반복 계산이 엄청 많다는 것이고 이는 메모이제이션을 통해서 어느 정도 해결할 수 있다. 메모이제이션에 대해서는 여러 차례 다룬 바 있으므로 자세한 설명은 생략하고 코드만 보이면 아래와 같다.
memo = dict()
def coin_combs(n, coins):
result = set()
# 사용가능한 동전들이 키의 일부가 되어야해서 튜플로 고정한다.
available_coins = tuple(sorted([coin for coin in coins if n >= coin]))
## 사용 가능한 동전들과 n의 조합으로 캐시를 찾는다.
if (n, coins) in dict:
return memo[(n, coins)]
for coin in available_coins:
if n > coin:
temp_result = coin_combs(n-coin, available_coins)
temp_result = {tuple(sorted(list(x) + [coin])) for x in temp_result}
else:
temp_result = { (coin, ) }
result = result.union(temp_result)
## 계산 결과를 캐시한다.
memo[(n, available_coins)] = result
return resultDynamic Programming
그런데 사실 이 동전 나누기 문제는 동적 계획의 전형적인 문제이다. 실제 오일러 프로젝트 풀이 포스팅에서도 이 기법을 사용했고, 복잡도 자체가 매우 낮기 때문에 엄청난 속도로 문제를 푼다. 보통 동적 계획법은 메모리 공간을 더 사용하여 속도를 내는 형태인데, 여기서는 접근법 자체가 점화식과는 달리 좀 특이하기 때문에 소개한다.
다른 접근 방법
이전의 접근 방법은
이 상황에서 10원을 만드는 방법의 개수를 이미 계산해놓은 값들을 사용해서 구하는 것이다. P(9)의 각 방법에 대해서 1원짜리 동전을 하나씩 더 넣는다. 그러면 각 방법들은 모두 10원을 만드는 방법이 된다. P(8)의 각 방법에 대해서는 2원짜리 동전을 하나씩 더 넣는다. 이 방법들도 모두 10원을 만드는 방법이 된다. 다시, P(5)의 각 방법에 대해서도 5원을 하나씩 넣는다. 이렇게하면 10원을 만드는 방법을 모두 찾은 셈이다. 왜냐하면 6원이나 7원의 조합인 상태에서 1, 2, 5원 중 동전 하나만 사용해서 10원을 만들 수 있는 방법은 없기 때문이다.
즉 n 원을 만드는 방법은 각 동전에 대해서 그 동전을 1개 사용한 가지수와 사용하지 않은 가지수로 나뉘는데, 그 동전을 사용하지 않은 가지수는 (n – 액면가)의 금액을 그 동전을 1개 덜 사용했을 때의 가지수와 같다. 따라서,
- 동전의 액면가가 작은 순서대로 시작하여
- 사실 이 방법은 0원 (
)을 만드는 방법 1가지와 같은 방법이다.
)원을 만드는 방법과 같은 수의 방법을 가질 수 있다. (물론 이게 전부가 아니라, 더 추가될 것이다.)
- 두번째로 작은 액면가
를 생각해보자.
를 만드는 가지수와 같을 것이다. (즉
원을 만드는 방법의 수와 같다.
- 이런식으로 새 동전에 대해서 해당 동전의 액면가 금액 부터, 그 동전을 사용하지 않은 가지 수(기존 값)에 그 동전을 사용하는 가지수 (액면가 만큼 작은 액수를 만드는 가지수)를 더해나가면 된다.
이를 코드로 구현하기 위해서는 배열을 하나 준비한다. 배열의 각 인덱스는 금액을 가리킨다. 위 접근법 2번에 의해 0번 인덱스의 값은 1이며, 나머지 인덱스의 값들은 모두 0의 값을 가진 상태로 초기화된다. 여기에는 a, b, c, d, e … 등 각 액면가의 동전을 사용한 가지수를 더해 나가게 되고, 이는 다음 동전에 대해서는 해당 동전을 사용하지 않고 그 금액을 만든 가지 수가 된다. 이를 코드로 옮기면 아래와 같고, 굳이 실행해보지 않아도 위의 코드와 비교했을 때 어떤게 더 빠른지 알 수 있을 것이다.
coins = (1, 2, 5, 10, 50 100)
ways = [1] + [0] * 200
for coin in coins:
for i in range(coin, 201):
ways[i] += ways[i - coin]
print(ways[-1])