오일러 프로젝트 76

76번 문제는 예전 31번(영국화폐 조합의 수)와 사실상 같은 문제이다. 임의의 자연수 N 을 N보다 작은 자연수들의 합으로 나타내는 경우의 수를 분할수라고 하는데, 이는 결국 1…N-1 의 액면가를 가지는 동전들로 N 만큼의 금액을 만드는 것과 동일한 연산이다.

오일러 프로젝트 76 더보기

오일러프로젝트78

동전 100개를 나누는 방법

이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다.

5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다.

ooooo  # 5개짜리 그룹 1개
oooo o  # 4개 + 1개
ooo oo  # 3개 + 2개
ooo o o # 3개 + 1개 + 1개
oo oo o # 2개 + 2개 + 1개
oo o o o # 2개 + 1개 + 1개 + 1개
o o o o o # 1개 + 1개 + 1개 + 1개

이렇게 동전 n개를 나눌 때의 나누는 방법의 가짓수를 p(n)이라 할 때, p(n)이 백만으로 나누어 떨어지는 최소의 n은 얼마인가?

접근

동전을 나누는 문제에 대해서 나눠진 각 그룹을 해당 그룹의 동전수로 치환하면  n을 n이하의 자연수의 합으로 나타내는 가지수와 같은 문제가 된다. 따라서 위의 도식은 아래와 같이 표현할 수 있게 된다.

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

이는 동전의 종류가 1, 2, 3, 4, 5원이 있을 때 5원을 만드는 방법의 가지수와 동일하므로 결국 영국화폐조합1의 문제로 귀결된다. 따라서 n에 대해서 p(n)을 구하는 방법은 동적프로그래밍을 사용하여 풀 수 있고, 이는 아래의 코드로 표현할 수 있다.

def getWays(target):
    ways = [1] + [0] * target
    values = range(1, target+1)
    for value in values:
        for i in range(value, target+1):
            ways[i] += ways[i-value]
    return ways[-1]

print getWays(5)

문제는 이걸 가지고 값이 100만으로 나눠떨어지는 시점을 계산해야 한다는 점이다. n의 범위를 알 수 없기 때문에 좀 골치가 아픈 문제이다. 일단 무식하게 i = 2 부터 시작해서 1백만으로 나눠떨어지는 지점까지 찾아서 실행해보자.

i = 2
while True:
    w = getWays(i)
    if w % 1000000 == 0:
        print i, w
        break
    i += 1

뭐 이렇게 해놓고 마냥 기다렸을 때 언제 끝날지 모를 정도로 오래 걸린다. 동적 프로그래밍의 특성상 n에 대해서 P(n)을 구할 때는 재귀적인 방법들보다는 빠르게 계산할 수 있지만, 여기서는 n이 계속 바뀌기 때문이다. 따라서 n보다 작은 케이스부터 차례대로 계산하기 때문에 n이 커지면 커질수록 전체 계산시간은 지수적으로 증가하고, 이 루프에 있어서는 부분 문제를 중첩하는 방법을 찾기가 까다롭다.

찾을 수 있을지도 모르겠다. 이 부분은 더 고민이 필요할 듯 하다.

충분히 큰 수 M에 대해 계산한다면, M보다 작은 값 중에서 답이 있다면 오랜 시간이 걸리지 않을 수 있다. 하지만 M이 얼마가 될지 모르기 때문에 여기서 막히게 된다.

대안

그렇다면 작은 n에 대해서 P(n)을 계산해 나가면서 이전에 계산했던 값을 재활용할 수 있는 방법이 있는지 살펴보자. 어쨌거나 반복계산을 엄청나게 수행하는 것 보다는 이게 나을 것 같다. 동적 프로그래밍에 의해 값을 계산하는 과정을 추적해보면, 모종의 규칙을 발견하게 될지도 모르겠다.

이를 위해서 내가 세워본 룰은 다음과 같다.

  1. 각 n에 대해 가지수를 저장하는 배열 ways는 첫 원소가 1이고 나머지는 0으로 채워진 target + 1 만큼의 길이를 가지고 있다.
  2. 그리고 n 번째 항을 계산할 때는 n 보다 작은 자연수인 values의 각 value 값에 대해서 value 값 만큼 적은 인덱스의 값을 누적해서 더해주게 된다.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0

초기 값은 이런 형태가 된다. 자 그래서 1개짜리 그룹을 포함하는 경우는 각 n에 대해서 (n-1)번째의 현재값을 더한 것이 된다. 물론 이는 중간 과정이며, n=1,2,3… 의 순으로 각각 더해준다. 여기까지의 결과는 아래와 같고, 따라서 P(1) = 1 이 된다.

value: 1
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1

계속해보자. 이번엔 2개짜리 그룹을 사용하느냐의 여부다. 이는 각 n에 대해서 (n-2)위치의 값을 더해주는 계산을 한다.  2의 맨 아래에는 0번의 값을 더했고, 4의 맨 아래에는 2에서 계산된 결과를 더했다.

value: 2
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   2 .... ?

이제 P(2)=2로 계산됐다. 3부터 계속 채워나가 보자.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   3 .... ?
            1   1   2   3
                1   1   2
                    1   1
                        1

그래서 p(4) = 4, p(5) = 7, p(6) = 11 이 나오게 된다. (각 n에 대해서 해당 열의 세로로 나열된 숫자들의 합이 된다.) 그럼 이 값에서 p(7)을 계산할 수 있을까?  만약 아래와 같이 p(n)을 구하는 과정에서 총 합만을 남기는 것이 아니라, 모든 단계의 값을 분리해서 보관한다면 가능할 것 같다.

0   1   2   3   4   5   6 .... 7
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1 --> p(6)중 0, 1 의 합
        1   1   2   2   3 .... 3 --> p(5)중 0, 1, 2 의 합 
            1   1   2   3 .... 4 --> p(4)중 0, 1, 2, 1 의 합
                1   1   2 .... 3 --> p(3)중 0, 1, 1, 1 의 합
                    1   1 .... 2 --> p(2)중 0, 1, 1 의 합
                        1 .... 1 --> p(1)중 0, 1의 합 
                               1 --> p(0)중 1의 합 

그렇다면 각 ways[n] 의 각 항이 단일 정수값이 아니라 리스트라면, p[n] = [ p[n-1][:2], p[n-2][:3], p[n-3][:4] ... p[0][:n]]  이 된다.

그럼 계산 과정의 수열들을 보존하고, 다음 항을 계산할 때 값을 추가해나가는 식으로 계산하는 코드를 짜보자.

class Dist(object):
    def __init__(self):
        self.n = 0
        self.ways = [[1]]

    def expand(self):
        self.n += 1
        self.ways.append([0])
        for value in range(1, self.n+1):
            self.ways[self.n].append(sum(self.ways[self.n-value][:value+1]))
        return sum(self.ways[self.n])

d = Dist()
for i in range(1, 11):
    print i, d.expand()

이를 실행해서 돌려보면 1~10 사이의 값에 대해서는 P(n)을 잘 구해준다. 하지만 이렇게 돌려서 구현한 목적은 “계산을 빠르게”하기 위한 것이었는데, n이 커지면 커질 수록 계산에는 여전히 많은 시간이 소요된다. (리스트에 대한 append 라든지 하는 부분들이 비용이 꽤나 큰 연산이다.) 실제로 계산해보면 이 방식도 너무나 느리다. 게다가 이 문제는 그 값 역시 엄청나게 커지기 때문에 큰 정수 연산이 들어가면서 계속 문제가 된다. 실제로는 백만으로 나눈 나머지만 확인하면 되기 때문에 백만 이상의 값은 버리도록 튜닝을 해 보아도 이렇게 풀어서는 답이 안나온다. 다른 접근법이 필요하다.

또다른 접근 : 분할수에 관련된 정리

특정 수를 다른 수의 합으로 표시하는 것을 분할수라고 한다. 분할수 관련해서 구글링을 해보면 오각수정리라는 것을 만날 수 있다. 이 정리는 보통 아래와 같은 수식으로 표현된다.

 p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots

이 때 1, 2, 5, 7은 오각수의 수열이며, 이 수열이 n보다 작을 때까지   P(n-k)들의 값을 더하거나 빼서  P(n)을 만들 수 있다는 것이다.  즉, 이를 정리하면 아래의 식이 된다.

 p(n) = \sum _{k} (-1)^{k-1}p(n-g_{k})  

이 때 g_{k}는 1, -1, 2, -2, 3, -3… 의 수열의 각 항을 이용해서 오각수 공식에 대입하여 얻은 수이다. 다음과 같이 정의한 함수를 통해서 얻을 수 있다.

def getPenta(k):
    # n: 1, -1, 2, -2, 3, -3 ...
    n = (k/2 + 1 if k % 2 == 0 else (k / 2)* -1 - 1)
    return n*(3*n - 1) / 2

이 수열은 다음과 같이 나온다.

1
2
5
7
12
15
22
26
35
40

그럼 이제 일반항을 구하는 생성함수를 보자.

 p[n] = p[n-1] + p[n-2] - p[n-5] - p[n-7] + p[n-12] ....

이런 식으로 이어지며, 이 때 p[0] = 1, p[음수] = 0 으로 처리된다. 즉 g_{k}가 n 보다 작아지는 상황이 오면 계산이 종료된다고 보면 된다. 또한 각 항의 부호는 +, +, -, – 의 패턴으로 반복된다. 따라서 일반항을 구하는 함수를 다시 써보면 아래와 같이 정리할 수 있다. (역시 동적계획법이지만 연산의 수가 훨씬 적다)

def getP(n):
    signs = (1, 1, -1, -1)
    p = [1] + [0] * n
    for k in range(1, n+1):
        pk = 0 # p[k]의 항이 될 값
        i = 0 # 점화식 내의 부분 수열의 인덱스
        penta = getPenta(i) # gk
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        p[k] = pk
    return p[-1]

최종장

이제 이 문제의 답 구하는 작업에 다시 도전해보도록 하자. 위의 함수는 n 번까지만 루트를 돌지만 무한루프를 돌면서 조건을 만족할 때까지 100만으로 나눠지는 항이 있는지 찾는다. . 또한 큰 정수 연산에 대한 부담을 줄여서 연산 속도를 빠르게 하기 위해서 p[k] 항에는 100만으로 나눈 나머지만 저장하도록 하겠다.

def main():
    signs = (1, 1, -1, -1)
    p = [1]
    while True:
        k = 1
        pk = 0
        i = 0
        penta = getPenta(i)
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        pk = pk % 1000000
        if pk == 0:
            print k
            return
        p.append(pk)

 

기대와 달리 엄청 빠르게 답이 나오지 않지만 (대략 10~13초 가량 소요된다) 그럼에도 불구하고 처음 몇 번의 시도에 비해서는 상당한 발전이다.

오일러 프로젝트 31 – 영국 동전의 액면가 조합 문제 관련 해설

오일러 프로젝트 31번 문제의 풀이는 해당 포스트에서 보면 허무하리만치 짧고 간단하며, 어찌보면 굉장히 이해하기 힘든 식으로 코드가 짜여져 있다. 게다가 재귀라든지 여러가지 그외 방법으로 푸는 것 보다 속도도 엄청 빠르다. (당연할 것이 재귀 호출 같은 것은 전혀 생각하지 않고 그저 정수 배열의 일부 항끼리 서로 더해나가는 2중 루프가 전부이다.) 이런 괴상한 풀이는 어떻게 나오게 되었으며, 어떤 식으로 알고리듬을 짠 것일까?

오일러 프로젝트 31 – 영국 동전의 액면가 조합 문제 관련 해설 더보기