이쁜왕자 만쉐~~
[C언어] 파티션 생성기 (partition generator) 본문
여기서 파티션(partition)은 하드디스크 파티션이 아니라 수학의 정수론에 나오는 파티션이다.
파티션이란 어떤 수를 여러개의 0보다 큰 정수로 자르는 방법에 대한 내용이다. 예를 들어 4 라는 수는 4, 3+1, 2+2, 2+1+1, 1+1+1+1 이라는 5가지 방법으로 표현할 수 있다. 작은 수는 손으로 해도 되지만, 수가 커질수록 손으로 할만한 수준이 아니게 된다. 예를 들어 n = 10 일때는 겨우 42 가지밖에 안되지만, n = 100 인 경우는 1억 9천만 가지의 분할 방법(정확히는 190569292)이 존재한다. 이쯤 되면 컴퓨터의 도움 없이 뭔가를 한다는 건 불가능하다.
여하튼, 10개의 동전이란 이름의 퍼즐 문제 (얼마전에 n=10 인 경우를 잉여력을 발휘하여 손으로 풀어서 그림 그린 적이 있다.
) 를 풀다 보니, 주어진 수에 대해서 모든 파티션을 다 구해야 했다. 이런 걸 구하는 방법에 대한 것은 보통 generator 라고 부르니깐, 구글에 partition generator 라고 검색해 보았다. 몇가지 결과가 튀어나왔지만, 딱히 쓸만해 보이진 않았다. (즉, 읽어봐도 뭔 소린지 이해를 못했다는 뜻이다.) 그래서 신경 끄고 있었다.
신경 끄고 잠시 잊고 있다가, 다시 생각나서 무식하게 짜보기로 했다. 그리고, 구조상 재귀 호출로 짜면 뭔가 튀어나올것 같았다. 실제로 짜보니 100줄도 안되는 아주 심플한 코드가 튀어 나왔다. 사실 제네레이터를 제대로 구현하려면, 한번 호출할때 마다 그 다음 파티션이 토큰처럼 하나씩 튀어 나오게 해야 하지만, 기본적인 알고리즘만 알고 있다면 그렇게 바꾸는게 어려운건 아니니, 내가 알바 아니다. 그냥 무식하게 다 찍도록만 작성했다. 배열을 n+1 크기로 잡고, 젤 앞에 1을 넣어 놓고 쓰는 별 의미 없는 최적화 기법 한가지를 제외하고서는 코드 상으로 어려울 것도 없다.
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int print_partition(int arr[], int pos)
{
int i;
for (i=0;i<pos;i++)
printf(" %d", arr[i]);
printf("\n");
return 0;
}
int partition(int arr[], int n, int pos, int *pcnt)
{
int i;
if (n == 0)
{
(*pcnt)++;
print_partition(arr, pos);
}
else
{
for(i=arr[pos-1]; i<=n; i++)
{
arr[pos] = i;
partition(arr, n-i, pos+1, pcnt);
}
arr[pos] = 0;
}
return 0;
}
int do_partition(int n)
{
int cnt = 0;
int *arr = malloc( (n+1)*sizeof(int) );
if (arr == NULL)
exit(0);
arr[0] = 1;
partition(arr+1, n, 0, &cnt); /* arr+1, tricky */
free(arr);
return cnt;
}
int main()
{
int cnt;
cnt = do_partition( 10 );
printf("----------\n cnt = %d\n", cnt);
return 0;
}
컴퓨터공학과 대학생에게 프로그래밍 과제로 내기에 딱 적당한 수준이다. 다만, 수학이랑 전산을 같이 배우지 않으면 문제 자체를 이해 못할 가능성이 좀 있다.
여튼, 재귀 호출은 뭔가 참 재미있는 프로그래밍 기법인것 같다. 재귀 호출은 함부로 쓰기에는 꽤나 위험하고, 이해하기도 쉽지 않고, 무엇보다 디버깅하기에 골치 아프지만, 잘쓰면 정말 깔끔한 코드가 만들어 진다.
그러고 보니, 오래전에 prime ring problem 에 관련된 글을 쓴 적이 있는데. (
) 그때도 뭔가 이런 저런 고민을 해가며 짜보았지만, 결론적으로 재귀호출을 이용해서 무식하게 짜는게 훨씬 빠른 결과를 냈던 기억이 있다.
- 이쁜왕자 -
- Valken the SEXy THief~~ ^_* -
