[궁극의 웰노운 알고리즘] 11. Partition number, Euler's Pentagonal Theorem

저번 글에서 예고한 대로, 궁극의 웰노운 알고리즘을 작성한다. 사실 이 주제에 대해서는 굳이 글을 쓸 생각은 없었다만, 그래도 나름 알고있으면 아주 못써먹을 정도는 아닌 알고리즘이라고 생각되어 포스팅하는 것이 낫다는 결론에 이르렀으며, 무엇보다 문제를 풀다가 한 번 더 마주치게 된 알고리즘이라서 포스팅하게 되었다.

 

1. Introduction

다음과 같은 문제를 생각하자:

 

정수 \( n \)이 주어진다. 당신은 \(P(n)\)(즉, \(n\)번째 분할수)을 출력해야 한다.

 

분할수에 대한 기초적인 이론은 중등 KMO 수준에서도 자주 다루기 때문에 이 문제가 그리 어렵지 않게 풀릴 것이라고 예상할 수도 있지만, 생각보다 이 문제는 빠른 시간 내에 해결하는 것이 쉽지 않다. 

 

아, 참고로 분할수라는 것이 무엇인지 모르는 독자들을 위해서, 위키를 참조한다. 다만 너무 아래까지 보면 스포이므로, 그냥 정의만 이해하는 것을 추천한다(물론 포스팅을 다 보고 이해가 가지 않는다면 그때는 참고해도 좋다.). (https://en.wikipedia.org/wiki/Partition_function_(number_theory))

Partition function (number theory) - Wikipedia

 

암튼, 결국 \(P(n)\)을 제곱보다 빠르게 구할 수 있느냐가 주요한 궁금증이다. 그리고 이를 가능하게 해주는 것이 바로 오일러의 오각수 정리이다.

 

우선, 가장 기초적인 것부터 시작하자. \(P(n)\)의 의미에 대해 생각해보면, 적절한 조합론적 대응을 통해서 \(P(n)\)이 \((1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)...\)의 \(n\)번째 계수라는 것을 이해할 수 있다(이는 생성함수적인 논의인데, 생성함수에 대해 잘 모른다면 이항계수 \(\binom{n}{k}\)가 \((1+x)^n\)의 \(k\)번째 계수가 되는 것과 비슷한 맥락이라고 생각하면 된다.).

 

아무튼, 우리가 한가지 더 알고 있는 사실은, 일반적으로 널리 알려진 기초적인 수학적 사실을 기반으로 \(1+x^a+x^{2a}+x^{3a}+...\)는 적당한 \(x,a\)의 범위에서 \(\frac{1}{1-x^a}\)와 같이 나타낼 수 있다는 것이다. 이를 통해, 모든 수렴/발산 여부를 무시하고 식을 정리해보면 \(P(n)\)이라는 것은 \(\frac{1}{(1-x)(1-x^2)(1-x^3)...}\)의 \(n\)번째 계수임을 알 수 있다.

 

그렇다면, 남은 문제는 두 가지인데,

 

1. \((1-x)(1-x^2)(1-x^3)...\)을 빠르게 계산할 수 있는가?

2. 위 다항식의 역수를 빠르게 계산할 수 있는가?

 

2번은 잘 알려진 다항식 연산들을 열심히 계산하면 어떻게든 처리가 되기야 할 것이고, 1번 또한 사실 다항식의 로그연산과 지수연산을 열심히 적용하면 계산할 수 있다고 알려져 있지만, 이런식으로 구하는 것이 유일한 길인 것을 여러분은 원치 않을 것이다.

 

2. Euler's Pentagonal Theorem

그런 독자들을 위해, 오일러의 오각수 정리가 있다. 이 정리의 statement는 굉장히 단순한데, 묘사하자면 다음과 같다:

 

\((1-x)(1-x^2)(1-x^3)...=1+\sum_{k=1}^{\infty}(-1)^k(x^{\frac{k(3k+1)}{2}}+x^{\frac{k(3k-1)}{2}})\)

 

이 포스팅에서 해당 정리의 자세한 증명은 생략한다. 아무튼 중요한 것은, 이 정리를 어떻게 활용할 수 있는가가 될 것이다.

 

일단, 위에서 언급한 1번 문제가 굉장히 단순하게 해결된다는 사실을 알 수 있다. 왜냐하면, 기존에는 다항식을 서로 곱해야 했던 문제가, 이제는 그냥 특정 인덱스에 +-1을 박아주는 문제로 환원되었기 때문이다. 그렇다면 거기에 2번을 즉각적으로 적용해서 위보다는 조금 더 단순한 \(O(nlog(n))\) 솔루션을 얻어낼 수 있다.

 

그러나, 여전히 우리는 다항식의 역수를 계산한다는 끔찍한 과제를 해결해야만 한다. 이러한 다항식연산을 완전히 우회할 수 있는 방법은 존재하지 않을까?

 

다행히도, 그런 방법이 존재한다. 결국 \(P(n)\)에 대한 생성함수가 \(\frac{1}{(1-x)(1-x^2)(1-x^3)...}\)이기 때문에, \(P(n)\)의 생성함수는 \(\frac{1}{(1-x)(1-x^2)(1-x^3)...}\)와 곱해졌을 때 1이 될 것이다. 즉, \((1+\sum_{k=1}^{\infty}(-1)^k(x^{\frac{k(3k+1)}{2}}+x^{\frac{k(3k-1)}{2}}))(\sum_{k=0}^{\infty}P(k)x^k)=1\)라는 것인데, 그렇다면 상쇄되는 각 항들을 잘 살펴보면 \(P(n)=\sum_{k=1}^{???}(-1)^{k-1}(P(n-\frac{k(3k+1)}{2})+P(n-\frac{k(3k-1)}{2}))\)와 같은 식을 얻는다. 여기에서 ???부분은 잘 생각해보면 \(O(\sqrt{n})\)정도임을 손쉽게 유추할 수 있기 때문에, 이제 아무런 다항식 연산 없이 위의 재귀식을 나이브하게 돌리는 것만으로 분할수를 \(O(n\sqrt{n})\)만에 계산할 수 있다!

 

사실, PS에서 분할수를 깡으로 구하는 것을 요구하는 문제가 그렇게 많은 편은 아니긴 해서 막상 이걸 쓰기엔 막막하긴 한데, 일단 다음과 같은 문제를 해결할 때에는 요긴하게 사용할 수 있다:

 

(https://www.acmicpc.net/problem/8353)

 

문제를 읽어보면 대충 분할수를 구하면 모든것이 아주 쉽게 해결된다는 사실을 알 수 있으므로, 그냥 위의 재귀공식을 구현해서 짜면 답을 얻는다.

 

 

3. P.S.

학기동안 latex 작업을 할 일이 많았어서 극심한 고통을 받으면서 latex 문법을 익혔는데, 그런 여파인지는 몰라도 수식을 쓸 때 자연스럽게 latex 처리를 전보다 많이 하게 된 것 같다.