성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Roll A Lisp In C - Reading ; https...
[정성태] Java - How to use the Foreign Funct...
[정성태] 제가 큰 실수를 했군요. ^^; Delegate를 통한 Bein...
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>동전을 여러 더미로 나누는 경우의 수 세기(Partition Number) - 두 번째 이야기</h1> <p> 저번 글에서 점화식을 언급하면서 이야기를 끝냈는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 동전을 여러 더미로 나누는 경우의 수 세기 ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/1271'>http://www.sysnet.pe.kr/2/0/1271</a> </pre> <br /> 이와 관련해서 한번 정리를 해야지... 막연히 생각만 하다가 오늘 우연히 다음의 글을 보았습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Enumerating integer compositions (the return of the binomial coefficients) ; <a target='tab' href='http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx'>http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx</a> </pre> <br /> 저 글을 보면서 "<a target='tab' href='http://www.sysnet.pe.kr/2/0/1271'>동전을 여러 더미로 나누는 경우의 수 세기</a>"가 생각났던 것입니다. 그럼 한번 정리를 해볼까요? ^^<br /> <br /> 우선, "<a target='tab' href='http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx'>Enumerating integer compositions (the return of the binomial coefficients)</a>" 글에서 언급된 동전 나누기 경우의 수를 세는 것을 보겠습니다. 글의 본문에 나오듯이 숫자 3에 대해 다음과 같이 쪼개는 것을 볼 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > * * * 3 *|* * 1+2 * *|* 2+1 *|*|* 1+1+1 </pre> <br /> 사실 이렇게 나누는 것은 쉽습니다. ^^ (제 짧은 수학 지식으로도 예전에 읽었던 통계 책의 기억에 따라) 나누는 기준을 '칸막이'라고 생각하면 쉽다는 것을 알 수 있습니다. 게다가 2진 코드에 익숙한 우리네 개발자들이라면 칸막이의 유무를 비트로 생각하면 더욱 이해가 쉽습니다.<br /> <br /> 즉, 다음과 같이 0과 1로 대체해 보면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > * * * 3 0 0 *|* * 1+2 1 0 * *|* 2+1 0 1 *|*|* 1+1+1 1 1 </pre> <br /> 00, 10, 01, 11의 경우로 나오는데요. 그렇습니다. 바로 그 익숙한 2진수입니다. 따라서 n개의 동전인 경우 그것을 나누기 경우의 수는 2<sup>(n - 1)</sup>로 간단하게 구할 수 있습니다. 위에서는 n == 3이기 때문에 2<sup>(3 - 1)</sup>이므로 4가 나오는 것입니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> 동전 나누기 이야기를 더 하기 전에 "<a target='tab' href='http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx'>Enumerating integer compositions (the return of the binomial coefficients)</a>" 글의 제목에 나온 "이항 계수(binomial coefficient)"에 대해 잠시 알아보겠습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 이항계수 ; <a target='tab' href='http://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98'>http://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98</a> [알고리즘] 동적프로그래밍 Part 1 - 이항 계수 문제 (Binomal Coefficient) ; <a target='tab' href='http://destiny738.tistory.com/194'>http://destiny738.tistory.com/194</a> </pre> <br /> 위의 글에서도 나오지만 이항계수는 "n개의 서로 다른 물건 중에서 순서 없이 k개를 뽑는 조합의 가짓수"입니다. 즉, 우리가 많이 알고 있던 nCr의 문제이고 따라서 다음의 공식으로 구해집니다.<br /> <script type="math/tex">\begin{pmatrix}n \\ k\end{pmatrix} = \frac{n!}{k!(n-k)!} \hspace{35pt} if \hspace{15pt} n \geq k \geq 0 \hspace{45pt}</script> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > [MathJax] <span class="mathjax-preview">\begin{pmatrix}n \\ k\end{pmatrix} = \frac{n!}{k!(n-k)!} \hspace{35pt} if \hspace{15pt} n \geq k \geq 0 \hspace{45pt}</span> [Google Chart API] <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\begin{pmatrix}+n+\\+k\end{pmatrix} = \frac{n!}{k!(n-k)!} \hspace{35pt} if \hspace{15pt} n \geq k \geq 0 \hspace{45pt}"> <br /></pre> <br /> 정의에 따라 이 식을 그대로 factorial 계산을 이용해 구할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > using System; using System.Numerics; class Program { static void Main(string[] args) { // 7개 중에서 3개를 뽑는 조합의 가짓수 == 7C3 Console.WriteLine(<span style='color: blue; font-weight: bold'>7.C(3)</span>); // 출력 결과: 35 } } static class IntExtension { public static BigInteger C(this int n, int k) { return n.Factorial() / (k.Factorial() * (n - k).Factorial()); } public static BigInteger Factorial(this int n) { if (n == 0) { return 1; } BigInteger result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; } } </pre> <br /> 하지만 일반적으로 factorial은 계산량이 많기 때문에 재귀호출을 이용한 점화식을 쓰는 것이 효율적입니다. 아래의 글에 나오는 것처럼,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > History: 알고리즘 대회에 필요한 수학 - 이항계수 ; <a target='tab' href='https://algospot.com/wiki/old/561/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8C%80%ED%9A%8C%EC%97%90_%ED%95%84%EC%9A%94%ED%95%9C_%EC%88%98%ED%95%99'>https://algospot.com/wiki/old/561/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8C%80%ED%9A%8C%EC%97%90_%ED%95%84%EC%9A%94%ED%95%9C_%EC%88%98%ED%95%99</a> </pre> <br /> 이항 계수의 점화식이 있고,<br /> <br /> <script type="math/tex">\begin{pmatrix}n \\ k \end{pmatrix} = \begin{cases} \begin{pmatrix}n - 1 \\ k - 1 \end{pmatrix} + \begin{pmatrix}n - 1 \\ k \end{pmatrix} &\mbox { if } 0 < k < n \\ 1 &\mbox { if } \: k = 0 \: or \: k = n \end{cases} </script> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > [MathJax] <span class="mathjax-preview">\begin{pmatrix}n \\ k \end{pmatrix} = \begin{cases} \begin{pmatrix}n - 1 \\ k - 1 \end{pmatrix} + \begin{pmatrix}n - 1 \\ k \end{pmatrix} &\mbox { if } 0 < k < n \\ 1 &\mbox { if } \: k = 0 \: or \: k = n \end{cases}</span> [Google Chart API] <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\left( n \\ k \right) = "><img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\left \{ \left( n - 1 \\ k - 1 \right) %2b \left( n - 1 \\ k \right) \hspace{35pt} if \hspace{15pt} 0 < k < n \\ 1 \hspace{105pt} if \: k = 0 \: or \: k = n \right \}"> <br /></pre> <br /> <br /> 복잡하게 factorial 계산할 필요없이 곧바로 이 수식을 코드로 옮겨주면 결과가 나옵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > using System; using System.Numerics; class Program { static void Main(string[] args) { Console.WriteLine(7.BC(3)); // 7.C(3)과 결과가 같은 35 출력 } } static class IntExtension { public static BigInteger BC(this int n, int r) { if (r == 0 || r == n) { return 1; } return (n - 1).BC(r - 1) + (n - 1).BC(r); } } </pre> <br /> 그런데, 조합(Combination)하면 꼭 등장하는 것이 바로 "파스칼의 삼각형"입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 파스칼의 삼각형 ; <a target='tab' href='http://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95'>http://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95</a> </pre> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 1 1 1 <span style='color: blue; font-weight: bold'>1 2 1</span> <span style='color: blue; font-weight: bold'>1 3 3 1</span> 1 4 6 4 1 1 5 10 10 5 1 </pre> <br /> 잘 아시는 것처럼, 이 값은 이항 전개에서의 계수들의 값과 일치하기도 합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > (n + k)<sup>2</sup> = <span style='color: blue; font-weight: bold'>1</span> * n<sup>2</sup> + <span style='color: blue; font-weight: bold'>2</span>nk + <span style='color: blue; font-weight: bold'>1</span> (n + k)<sup>3</sup> = <span style='color: blue; font-weight: bold'>1</span> * n<sup>3</sup> + <span style='color: blue; font-weight: bold'>3</span>a<sup>2</sup>b + <span style='color: blue; font-weight: bold'>3</span>ab<sup>2</sup> + <span style='color: blue; font-weight: bold'>1</span> <script type="math/tex">(x+y)^n = \sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} x^ky^{n-k}</script> </pre> <br /> 뿐만 아니라, 파스칼의 삼각형이 각 줄마다 nCr의 조합에 해당한다는 것도 꽤나 유명하지요.<br /> <br /> <script type="math/tex">a_{nk} = \begin{pmatrix}n - 1 \\k - 1\end{pmatrix}</script> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > [MathJax] <span class="mathjax-preview">a_{nk} = \begin{pmatrix}n - 1 \\k - 1\end{pmatrix}</span> [Google Chart API] <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=a_{nk} = \begin{pmatrix}+n - 1+\\+k - 1+\end{pmatrix}"> <br /></pre> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 0C0 1C0 1C1 2C0 2C1 2C2 3C0 3C1 3C2 3C3 4C0 4C1 4C2 4C3 4C4 5C0 5C1 5C2 5C3 5C4 5C5 </pre> <br /> 즉 파스칼의 삼각형에 n번째 줄의 k번째 수는 각각 1씩 뺀 조합의 수와 일치하는 것입니다. 예를 들어, 5번째 줄의 3번째 값인 6은 (5 - 1)C(3 - 1)의 조합을 의미하고 결국 4C2의 값에 해당합니다.<br /> <br /> 따라서, 어렵게 재귀 호출을 할 필요도 없이 단순하게 파스칼의 삼각형 값만 갖는 자료 구조가 있는 경우 nCr의 수를 인덱스 번호만으로 바로 구할 수 있습니다. <br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > using System; using System.Collections.Generic; using System.Diagnostics; class Program { static void Main(string[] args) { Console.WriteLine(PascalTriangle(4, 2)); // 출력 결과: 6 } public static int PascalTriangle(int n, int r) { List<int[]> list = new List<int[]>(); for (int i = 0; i <= n; i++) { list.Add(new int[i + 1]); for (int j = 0; j < i + 1; j++) { if (j == 0 || j == i) { list[i][j] = 1; } else { list[i][j] = list[i - 1][j - 1] + list[i - 1][j]; } } } return list[n][r]; } } </pre> <br /> 가볍게 성능 테스트를 해볼까요? n == 30, r == 12로 한 경우 재귀 호출을 했던 2번째 방식이 가장 극악의 성능을 보여줬습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 팩토리얼 30.C(12) : 수행 시간 69 ticks 재귀호출 30.BC(12) : 수행 시간 32825809 ticks 파스칼 삼각형 : 수행 시간 35 ticks </pre> <br /> 소스 코드를 보면 알겠지만 팩토리얼의 경우 중간 결과값이 쉽게 int 범위를 벗어날 수 있으므로 BigInteger를 사용하는 탓에 파스칼 삼각형과 비교해 수행 시간이 아주 쪼~~~끔 밀리긴 했지만 가장 빠른 방식일 수 있습니다.<br /> <br /> 하지만, 파스칼 삼각형이 구성하는 것도 팩토리얼에 비해 뒤지지 않는 성능을 보이면서도, 일단 한번 구성된 이후로는 자연스럽게 캐시(Cache) 용도로 활용할 수 있기 때문에 성능상 가장 권장할 수 있는 방법입니다.<br /> <br /> 마지막으로, 파스칼의 삼각형은 다시 처음의 동전 더미 나누기와 연관이 됩니다. 왜냐하면 삼각형 구성에서 하나의 줄은 그 동전으로 뽑을 수 있는 모든 가짓수를 나타내기 때문입니다. 예를 들어, "<a target='tab' href='http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx'>Enumerating integer compositions (the return of the binomial coefficients)</a>" 글에서 다룬 3개의 동전 무더기를 나누는 경우의 수는 2C0, 2C1, 2C2의 가짓수의 합이 되고 처음에 언급했던 것처럼 이것은 2<sup>(n - 1)</sup>이 되는 것입니다.<br /> <br /> 결국, (학창시절에 배웠던 데로) 파스칼의 삼각형의 한 줄의 합은 2<sup>(n - 1)</sup>입니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> 자, 이제 다시 "프로젝트 오일러의 76, 78번 문제"에서의 동전 무더기 나누는 문제로 돌아오겠습니다. 이것은 중복된 동전 나누기를 허용하지 않으므로 경우의 수가 다릅니다. 예를 들어 3인 경우,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>3 2, 1</span> <span style='text-decoration: line-through'>1, 2</span> <span style='color: blue; font-weight: bold'>1, 1, 1</span> </pre> <br /> 위와 같이 "2, 1"과 "1, 2"에서 한 개만 포함하게 되는 것입니다. 이에 대해서는 별도로 "Partition Number"라는 문제로 바뀌게 되는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Partition (number theory) ; <a target='tab' href='http://en.wikipedia.org/wiki/Integer_partition'>http://en.wikipedia.org/wiki/Integer_partition</a> </pre> <br /> 그리고 이것이 오각수 정리와 연관된다는 것을 알 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Pentagonal number theorem ; <a target='tab' href='http://en.wikipedia.org/wiki/Pentagonal_number_theorem'>http://en.wikipedia.org/wiki/Pentagonal_number_theorem</a> </pre> <br /> 그래서 위의 글에 나온 Partition function을 보면 다음과 같은 함수가 나옵니다.<br /> <br /> <script type="math/tex">p(n)=\sum_{k}(-1)^{k-1}p(n-g_{k})</script> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > [MathJax] <span class="mathjax-preview">p(n)=\sum_{k}(-1)^{k-1}p(n-g_{k})</span> [Google Chart API] <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=p(n)=\sum_{k}(-1)^{k-1}p(n-g_{k})"> <br /></pre> <br /> 저 같은 사람은, 시그마 기호만 봐도 울렁증이 생기는데요. 다행히 이것을 쉽게 풀어 놓은 식이 함께 제공됩니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + ... </pre> <br /> 여기서 p 함수의 인자에 빼기 값으로 1, 2, 5, 7, ... 수열이 나오는데요. 이것이 바로 <a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=45'>프로젝트 오일러 45번 문제</a>에서 이미 소개된 오각수입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > P<sub>n</sub> = n (3n - 1) / 2 </pre> <br /> 단지, 오각수의 수열이 n = 1, 2, 3, 4, 5, ...을 대입하는 것과는 다르게 오일러의 오각수 정리에서는 n의 값으로 1, -1, 2, -2, 3, -3, ... 과 같은 식으로 대입을 하게 됩니다. 그런 경우 바로 우리가 p 함수에서 원했던 다음과 같은 수열이 나옵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, ... </pre> <br /> 오호~~~ 그럼 이제 문제를 푼 것이나 다름없습니다. 단지, 재귀 호출로 이뤄져 있기 때문에 약간 복잡한 면이 있는데, 정의에 따라 p 함수는 p(0) == 1이고, p(n < 0) == 0이므로 p(n)의 계산을 다음과 같이 할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > n == 1일때, p(1) = p(1 - 1) + p(1 - 2) - ... // 두 번째 p 함수에서 음수가 되었으므로 그 이후부터는 결과가 모두 0이 되므로 더 이상 수행할 필요가 없음. 따라서 p(1) == p(0) == 1 n == 2일때, p(2) = p(2 - 1) + p(2 - 2) - p(2 - 5) - ... // 세 번째 p 함수부터 0 결과 반환 p(2-1) == p(1) == 1 p(2-2) == p(0) == 1 따라서 p(2) == 2 n == 3일때, p(3) = p(3 - 1) + p(3 - 2) - p(3 - 5) - ... // 역시 세 번째 p 함수부터 0 결과 반환 p(3-1) == p(2), p(2)는 다시, p(2) == p(2 - 1) + p(2 - 2) - p(2 - 5) - ... p(2) == 2 p(3-2) == p(1) == 1 따라서 p(3) == p(2) + p(1) == 3 </pre> <br /> 어디... 이걸 C# 코드로 한번 만들어 볼까요? ^^<br /> <br /> 우선, 오각수 수열에 들어갈 n = 1, -1, 2, -2, 3, -3,... 값을 생성하는 것과 이를 오각수 식에 대입해서 나오는 결과 수열을 다음과 같이 IEnumerable 메서드로 반환할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public class Pentagonal { public IEnumerable<int> GenerateN() { int result = 1; while (true) { yield return result; yield return result * -1; result++; } // 1, -1, 2, -2, 3, -3,... 수열을 반환 } public IEnumerable<int> Numbers() { foreach (int k in GenerateN()) { yield return k * (3 * k - 1) / 2; } // 1, 2, 5, 7, ... 수열을 반환 } } </pre> <br /> 재료가 준비되었으니, 이제 재귀 호출 구문으로 오일러 함수를 만들어 주면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public class EulerFunction { public BigInteger P(int n) { BigInteger sum = 0; if (n == 0 || n == 1) { return 1; } Pentagonal pentagonal = new Pentagonal(); int sign = 1; foreach (int pentagonalNumber in pentagonal.Numbers()) { int diff = n - pentagonalNumber; if (diff < 0) { break; } if (sign % 4 == 1 || sign % 4 == 2) { sum += P(diff); } else { sum -= P(diff); } sign ++; } return sum; } } </pre> <br /> 이를 이용해 다음과 같이 자연스럽게 Partition Number 조합을 얻어낼 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > EulerFunction eulerFunction = new EulerFunction(); for (i = 2; i < 100; i++) { Console.WriteLine(i + ": " + eulerFunction.P(i)); } </pre> <br /> 물론, 이렇게 재귀호출로만 문제를 풀면 이항 계수를 얻어냈을 때 처럼 속도가 무척 느립니다. 위의 메서드는 단지 '원칙에 기반해 작성한 코드'이기 때문에 이해를 위해서만 사용하시고 ^^ 원하는 속도를 얻으려면 여기에 약간의 캐시(Cache)를 적용하면 훨씬 속도가 빨라집니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public class EulerFunction { <span style='color: blue; font-weight: bold'> static List<BigInteger> _pCache = new List<BigInteger>(); static EulerFunction() { _pCache.Add(1); // P(0) == 1 _pCache.Add(1); // P(1) == 1 }</span> public BigInteger P(int n) { BigInteger sum = 0; <span style='color: blue; font-weight: bold'> if (_pCache.Count > n) { return _pCache[n]; }</span> Pentagonal pentagonal = new Pentagonal(); int sign = 1; foreach (int pentagonalNumber in pentagonal.Numbers()) { int diff = n - pentagonalNumber; if (diff < 0) { break; } if (sign % 4 == 1 || sign % 4 == 2) { sum += P(diff); } else { sum -= P(diff); } sign ++; } <span style='color: blue; font-weight: bold'>_pCache.Add(sum);</span> return sum; } } </pre> <br /> 대단하군요. ^^ 이 코드로 "<a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=78'>Problem 78 (동전을 여러 더미로 나누는 경우의 수 세기)</a>" 문제를 풀면 1분 안에 10MB 남짓한 메모리만 써서 답을 얻을 수 있습니다. <a target='tab' href='http://www.sysnet.pe.kr/2/0/1271'>생짜로 구했을 때는 메모리가 4GB에 376초</a>가 소요되었는데. ^^<br /> <br /> (<a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=867&boardid=331301885'>첨부 파일은 이 글에 나온 모든 코드를 포함</a>하고 있습니다.)<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
7482
(왼쪽의 숫자를 입력해야 합니다.)