동전을 여러 더미로 나누는 경우의 수 세기(Partition Number) - 두 번째 이야기
저번 글에서 점화식을 언급하면서 이야기를 끝냈는데요.
동전을 여러 더미로 나누는 경우의 수 세기
; https://www.sysnet.pe.kr/2/0/1271
이와 관련해서 한번 정리를 해야지... 막연히 생각만 하다가 오늘 우연히 다음의 글을 보았습니다.
Enumerating integer compositions (the return of the binomial coefficients)
; http://blogs.msdn.com/b/oldnewthing/archive/2014/07/14/10541999.aspx
저 글을 보면서 "
동전을 여러 더미로 나누는 경우의 수 세기"가 생각났던 것입니다. 그럼 한번 정리를 해볼까요? ^^
우선, "
Enumerating integer compositions (the return of the binomial coefficients)" 글에서 언급된 동전 나누기 경우의 수를 세는 것을 보겠습니다. 글의 본문에 나오듯이 숫자 3에 대해 다음과 같이 쪼개는 것을 볼 수 있습니다.
* * * 3
*|* * 1+2
* *|* 2+1
*|*|* 1+1+1
사실 이렇게 나누는 것은 쉽습니다. ^^ (제 짧은 수학 지식으로도 예전에 읽었던 통계 책의 기억에 따라) 나누는 기준을 '칸막이'라고 생각하면 쉽다는 것을 알 수 있습니다. 게다가 2진 코드에 익숙한 우리네 개발자들이라면 칸막이의 유무를 비트로 생각하면 더욱 이해가 쉽습니다.
즉, 다음과 같이 0과 1로 대체해 보면 됩니다.
* * * 3
0 0
*|* * 1+2
1 0
* *|* 2+1
0 1
*|*|* 1+1+1
1 1
00, 10, 01, 11의 경우로 나오는데요. 그렇습니다. 바로 그 익숙한 2진수입니다. 따라서 n개의 동전인 경우 그것을 나누기 경우의 수는 2
(n - 1)로 간단하게 구할 수 있습니다. 위에서는 n == 3이기 때문에 2
(3 - 1)이므로 4가 나오는 것입니다.
동전 나누기 이야기를 더 하기 전에 "
Enumerating integer compositions (the return of the binomial coefficients)" 글의 제목에 나온 "이항 계수(binomial coefficient)"에 대해 잠시 알아보겠습니다.
이항계수
; http://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98
[알고리즘] 동적프로그래밍 Part 1 - 이항 계수 문제 (Binomal Coefficient)
; http://destiny738.tistory.com/194
위의 글에서도 나오지만 이항계수는 "n개의 서로 다른 물건 중에서 순서 없이 k개를 뽑는 조합의 가짓수"입니다. 즉, 우리가 많이 알고 있던 nCr의 문제이고 따라서 다음의 공식으로 구해집니다.
[MathJax]
\begin{pmatrix}n \\ k\end{pmatrix} = \frac{n!}{k!(n-k)!} \hspace{35pt} if \hspace{15pt} n \geq k \geq 0 \hspace{45pt}
[Google Chart API]
!} \hspace{35pt} if \hspace{15pt} n \geq k \geq 0 \hspace{45pt})
정의에 따라 이 식을 그대로 factorial 계산을 이용해 구할 수 있습니다.
using System;
using System.Numerics;
class Program
{
static void Main(string[] args)
{
// 7개 중에서 3개를 뽑는 조합의 가짓수 == 7C3
Console.WriteLine(7.C(3)); // 출력 결과: 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;
}
}
하지만 일반적으로 factorial은 계산량이 많기 때문에 재귀호출을 이용한 점화식을 쓰는 것이 효율적입니다. 아래의 글에 나오는 것처럼,
History: 알고리즘 대회에 필요한 수학 - 이항계수
; 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
이항 계수의 점화식이 있고,
[MathJax]
\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}
[Google Chart API]
 = )
 %2b \left( n - 1 \\ k \right) \hspace{35pt} if \hspace{15pt} 0 < k < n \\ 1 \hspace{105pt} if \: k = 0 \: or \: k = n \right \})
복잡하게 factorial 계산할 필요없이 곧바로 이 수식을 코드로 옮겨주면 결과가 나옵니다.
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);
}
}
그런데, 조합(Combination)하면 꼭 등장하는 것이 바로 "파스칼의 삼각형"입니다.
파스칼의 삼각형
; 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
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
잘 아시는 것처럼, 이 값은 이항 전개에서의 계수들의 값과 일치하기도 합니다.
(n + k)2 = 1 * n2 + 2nk + 1
(n + k)3 = 1 * n3 + 3a2b + 3ab2 + 1
뿐만 아니라, 파스칼의 삼각형이 각 줄마다 nCr의 조합에 해당한다는 것도 꽤나 유명하지요.
[MathJax]
a_{nk} = \begin{pmatrix}n - 1 \\k - 1\end{pmatrix}
[Google Chart API]
0C0
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4
5C0 5C1 5C2 5C3 5C4 5C5
즉 파스칼의 삼각형에 n번째 줄의 k번째 수는 각각 1씩 뺀 조합의 수와 일치하는 것입니다. 예를 들어, 5번째 줄의 3번째 값인 6은 (5 - 1)C(3 - 1)의 조합을 의미하고 결국 4C2의 값에 해당합니다.
따라서, 어렵게 재귀 호출을 할 필요도 없이 단순하게 파스칼의 삼각형 값만 갖는 자료 구조가 있는 경우 nCr의 수를 인덱스 번호만으로 바로 구할 수 있습니다.
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];
}
}
가볍게 성능 테스트를 해볼까요? n == 30, r == 12로 한 경우 재귀 호출을 했던 2번째 방식이 가장 극악의 성능을 보여줬습니다.
팩토리얼 30.C(12) : 수행 시간 69 ticks
재귀호출 30.BC(12) : 수행 시간 32825809 ticks
파스칼 삼각형 : 수행 시간 35 ticks
소스 코드를 보면 알겠지만 팩토리얼의 경우 중간 결과값이 쉽게 int 범위를 벗어날 수 있으므로 BigInteger를 사용하는 탓에 파스칼 삼각형과 비교해 수행 시간이 아주 쪼~~~끔 밀리긴 했지만 가장 빠른 방식일 수 있습니다.
하지만, 파스칼 삼각형이 구성하는 것도 팩토리얼에 비해 뒤지지 않는 성능을 보이면서도, 일단 한번 구성된 이후로는 자연스럽게 캐시(Cache) 용도로 활용할 수 있기 때문에 성능상 가장 권장할 수 있는 방법입니다.
마지막으로, 파스칼의 삼각형은 다시 처음의 동전 더미 나누기와 연관이 됩니다. 왜냐하면 삼각형 구성에서 하나의 줄은 그 동전으로 뽑을 수 있는 모든 가짓수를 나타내기 때문입니다. 예를 들어, "
Enumerating integer compositions (the return of the binomial coefficients)" 글에서 다룬 3개의 동전 무더기를 나누는 경우의 수는 2C0, 2C1, 2C2의 가짓수의 합이 되고 처음에 언급했던 것처럼 이것은 2
(n - 1)이 되는 것입니다.
결국, (학창시절에 배웠던 데로) 파스칼의 삼각형의 한 줄의 합은 2
(n - 1)입니다.
자, 이제 다시 "프로젝트 오일러의 76, 78번 문제"에서의 동전 무더기 나누는 문제로 돌아오겠습니다. 이것은 중복된 동전 나누기를 허용하지 않으므로 경우의 수가 다릅니다. 예를 들어 3인 경우,
3
2, 1
1, 2
1, 1, 1
위와 같이 "2, 1"과 "1, 2"에서 한 개만 포함하게 되는 것입니다. 이에 대해서는 별도로 "Partition Number"라는 문제로 바뀌게 되는데요.
Partition (number theory)
; http://en.wikipedia.org/wiki/Integer_partition
그리고 이것이 오각수 정리와 연관된다는 것을 알 수 있습니다.
Pentagonal number theorem
; http://en.wikipedia.org/wiki/Pentagonal_number_theorem
그래서 위의 글에 나온 Partition function을 보면 다음과 같은 함수가 나옵니다.
[MathJax]
p(n)=\sum_{k}(-1)^{k-1}p(n-g_{k})
[Google Chart API]
=\sum_{k}(-1)^{k-1}p(n-g_{k}))
저 같은 사람은, 시그마 기호만 봐도 울렁증이 생기는데요. 다행히 이것을 쉽게 풀어 놓은 식이 함께 제공됩니다. ^^
p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + ...
여기서 p 함수의 인자에 빼기 값으로 1, 2, 5, 7, ... 수열이 나오는데요. 이것이 바로
프로젝트 오일러 45번 문제에서 이미 소개된 오각수입니다.
Pn = n (3n - 1) / 2
단지, 오각수의 수열이 n = 1, 2, 3, 4, 5, ...을 대입하는 것과는 다르게 오일러의 오각수 정리에서는 n의 값으로 1, -1, 2, -2, 3, -3, ... 과 같은 식으로 대입을 하게 됩니다. 그런 경우 바로 우리가 p 함수에서 원했던 다음과 같은 수열이 나옵니다.
1, 2, 5, 7, 12, 15, 22, 26, 35, 40, ...
오호~~~ 그럼 이제 문제를 푼 것이나 다름없습니다. 단지, 재귀 호출로 이뤄져 있기 때문에 약간 복잡한 면이 있는데, 정의에 따라 p 함수는 p(0) == 1이고, p(n < 0) == 0이므로 p(n)의 계산을 다음과 같이 할 수 있습니다.
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
어디... 이걸 C# 코드로 한번 만들어 볼까요? ^^
우선, 오각수 수열에 들어갈 n = 1, -1, 2, -2, 3, -3,... 값을 생성하는 것과 이를 오각수 식에 대입해서 나오는 결과 수열을 다음과 같이 IEnumerable 메서드로 반환할 수 있습니다.
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, ... 수열을 반환
}
}
재료가 준비되었으니, 이제 재귀 호출 구문으로 오일러 함수를 만들어 주면 됩니다.
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;
}
}
이를 이용해 다음과 같이 자연스럽게 Partition Number 조합을 얻어낼 수 있습니다.
EulerFunction eulerFunction = new EulerFunction();
for (i = 2; i < 100; i++)
{
Console.WriteLine(i + ": " + eulerFunction.P(i));
}
물론, 이렇게 재귀호출로만 문제를 풀면 이항 계수를 얻어냈을 때 처럼 속도가 무척 느립니다. 위의 메서드는 단지 '원칙에 기반해 작성한 코드'이기 때문에 이해를 위해서만 사용하시고 ^^ 원하는 속도를 얻으려면 여기에 약간의 캐시(Cache)를 적용하면 훨씬 속도가 빨라집니다.
public class EulerFunction
{
static List<BigInteger> _pCache = new List<BigInteger>();
static EulerFunction()
{
_pCache.Add(1); // P(0) == 1
_pCache.Add(1); // P(1) == 1
}
public BigInteger P(int n)
{
BigInteger sum = 0;
if (_pCache.Count > n)
{
return _pCache[n];
}
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 ++;
}
_pCache.Add(sum);
return sum;
}
}
대단하군요. ^^ 이 코드로 "
Problem 78 (동전을 여러 더미로 나누는 경우의 수 세기)" 문제를 풀면 1분 안에 10MB 남짓한 메모리만 써서 답을 얻을 수 있습니다.
생짜로 구했을 때는 메모리가 4GB에 376초가 소요되었는데. ^^
(
첨부 파일은 이 글에 나온 모든 코드를 포함하고 있습니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]