이번에도 채점과 해설에 도움주신 황인욱(@nonblock) 님(『문제로 풀어보는 알고리즘』의 저자 중 한 분)께 감사의 마음을 전합니다.
—-
역시 생각보다 많은 분들이 트랙백을 달아 주셨습니다. 다들 재미있게 풀어주셔서 감사합니다. 풀어주신 내용들은 대부분 범위 안에서 잘 동작하네요. 아래에 간단한 설명입니다.
1. 문제의 아이디어
문제는 집합의 분할(partition of a set)을 모두 구하는 것입니다. 문제의 의도는 다음과 같습니다.
(1) 크기 n인 집합의 분할과 크기 n-1인 집합의 분할의 재귀적 관계를 이용할 수 있는가?
(2) 메모리를 적게 사용하여 모든 분할을 방문하는 코드를 작성할 수 있는가?
다음과 같은 관찰에서 분할을 만들어 낼 때, 이용할 수 있는 재귀적 관계를 얻을 수 있습니다. 다른 분들의 풀이에도 잘 나와 있습니다.
{0,1}을 나누는 방법은 다음 두 가지이다.
{{0}, {1}}
{{0, 1}}
이 때, {0, 1, 2}의 분할은 다음 두 가지로 구할 수 있다.
첫째, 또 다른 원소 2가 분할 중 한 집합에 들어갈 수 있다.
{{0}, {1}} 로부터
{{0, 2}, {1}}과 {{0}, {1, 2}}
{{0, 1}} 로부터
{{0, 1, 2}}
둘째, 또 다른 원소 2가 혼자서 새로운 집합을 만든다
{{0}, {1}} 로부터
{{0}, {1}, {2}}
{{0, 1}} 로부터
{{0, 1}, {2}}
모두 5가지.
이런 재귀적 관계를 이용하되, 크기가 n-1인 집합의 분할을 모두 만들어서 갖고 있다가 크기 n인 집합에 대한 분할을 만들도록 프로그램을 작성하면, n이 커짐에 따라 메모리 사용이 급격히 늘어납니다. 『문제로 풀어보는 알고리즘』 3장에 나와있는 방법들도 재귀적으로 모든 경우를 구하지만, 더 작은 문제의 모든 경우를 유지하면서 구해가지는 않습니다.
리스트나 집합을 자연스럽게 지원하는 고급언어의 특징을 이용해서 앞 단계 분할들을 유지하면서, 다음 단계의 집합을 생성하는 방법으로 하신 분들이 많았는데, n=16에서도 잘 나와서 할말은 없습니다. ^^
집합의 모든 분할을 살펴보면서 어떤 조건을 확인하는 경우에, 모든 분할을 메모리를 적게 쓰면서 빠르게 생성하는 것이 필요합니다. 여기에 대해서 생각해보는 것도 좋겠습니다.
2. 풀이 소개
작은 문제에 대한 결과 집합을 유지하는 대신에, 각 원소에 적절히 집합을 나타내는 번호만 잘 붙여서 재귀호출로 탐색해도 됩니다(분할들의 공간을 BFS대신에 DFS로 탐색하는 느낌으로). 이 때는 분할에 번호를 잘 붙여 재귀호출하면서, 모든 분할을 빠뜨리지도, 겹치지도 않게 표현하는 것이 중요합니다.
C로 작성해본 코드는 다음과 같습니다. (메인함수에서 “generate_partitions(arr, 0, n, 0);” 호출)
void print(int set[], int n, int nset)
{
int i, j;
for (i = 0; i < nset; i++) {
printf("{");
for (j = 0; j < n; j++)
if (set[j] == i)
printf("%d ", j);
printf("}");
}
printf("n");
}
void generate_partitions(int set[], int len, int n, int nset)
{
int i;
if (len == n) {
print(set, n, nset);
return;
}
// case 1
for (i = 0; i < nset; i++) {
set[len] = i;
generate_partitions(set, len + 1, n, nset);
}
// case 2
set[len] = nset;
generate_partitions(set, len + 1, n, nset + 1);
}
위에서는 크기가 n인 배열 하나만 사용하기 때문에, n이 아무리 커도 모든 결과를 다 만들어낼 수 있습니다. 다른 방법으로 이렇게 메모리 사용을 적게 하도록 작성해주신 포스팅들이 있었습니다.
여기서 좀 더 나가서, 집합의 분할을 특정한 수열을 빠짐없이 나열하는 문제로 보면, 재귀호출을 사용하지 않는 방법도 생각할 수도 있습니다. 다음의 포스팅을 참고하세요.
3. 참고자료
분할의 개수에 대해서는 참고할 만한 내용이 많습니다. 크기 n인 집합의 분할의 개수 B(n)을 벨 수(Bell Number)라고 부르는데, 다음 웹 페이지에서 설명을 보실 수 있습니다. 분할의 개수만 프로그램으로 구하는 것은 더 간단합니다.
http://mathworld.wolfram.com/BellNumber.html
비슷하게, 크기가 n인 집합을 k개의 부분집합으로 나누는 방법의 수 S(n, k)는 스털링 수(Stirling Number)라고 부르는데, 다음이 성립합니다(n>0).
S(n, k)=S(n-1, k) + S(n-1, k-1)
문제를 풀어보신 분들은 이제 이 점화식의 의미를 쉽게 이해하실 수 있을 겁니다!! S(n, k)를 더해서 B(n)을 계산할 수 있습니다.
여기서 설명한 방법에 대한 자세한 논의는 『The Art of Computer Programming 4A』에 잘 나와 있으나 이 책은 읽기 쉽지 않습니다(한빛미디어 4A 번역은 아직 나오지 않은 것으로 알고 있습니다). 스털링 수는 『Concrete Mathematics』 6장에서 나오니 참고하세요.
수고하셨습니다. ^^
도서출판 인사이트 