자연수 분할에 대해 알아보자
수분할
수분할은 자연수 n을 순서에 상관 없이 하나 이상의 자연수의 합으로 나타내는 방법이다. 그 중 일반적인 방법으로는 n/m 수분할이다. 이 방법은 n을 m이하의 자연수로만 나타내는 방법이다.
예시
예를 들어 5/2 수분할은
1+1+1+1+1
2+1+1+1
2+2+1
이렇게 된다. 이러한 n/m 수분할은 재귀적으로 생각할 수 있는데, 재귀적으로 생각하게 된다면 5/2 수분할에서 1+ 와 2+로 시작하는 부분 두 가지로 나눌 수 있다.
1) 1로 시작
1+1+1+1+1
2) 2로 시작
2+1+1+1
2+2+1
1+ 뒤에 나오는 1+1+1+1은 4/1 수분할과 같고, 2+뒤에 나오는 1+1+1, 2+1은 3/2 수분할의 두가지 이다. 따라서 이끌어낼 수 있는 점화식은 아래와 같다.
partition(0,m) = 1
if n>0 then, partition(n,m) = ∑(i=1 ~ m) partition(n-i,i)
소스코드
이러한 내용을 토대로 C언어로 함수를 작성하면,
int partition(int n, int m) {
int cnt = 0, i;
if (n < m) m=n;
if (n == 0) return 1;
for (i=1; i<=m; i++)
cnt += partition(n-i, i);
return cnt;
}
이러한 함수가 만들어진다. 하지만 중복계산이 계속 생겨서 효율적이지 못한 코드가 된다. 이 함수를 메모이제이션을 이용해서 바꾸어보자.
#define MAX 200
int memo[MAX][MAX];
int partition(int n, int m) {
int cnt = 0, i;
if (n < m) m=n;
if (memo[n][m] > 0) return memo[n][m];
if (n == 0) return memo[n][m] = 1;
for (i=1; i<=m; i++)
cnt += partition(n-i, i);
return memo[n][m] = cnt;
}
memo 배열에서 값이 0이라면 값이 계산된 적이 없기에 함수를 실행하고 그외의 다른 값이라면 도중에 해당 memo값을 반환해준다. 이러한 호출 구조는 그대로이며, 조금만 추가하면 중복 계산을 없앨 수 있다.
수분할에 덧셈의 순서를 구분하게 되는 코드도 가볍게 보았다.
int partition2(int n) {
int cnt = 0, i;
for (i=1; i<n; i++)
cnt += partition2(n-i);
return cnt + 1;
}