[재귀 알고리즘] n/m 수분할

 

[재귀 알고리즘] n/m 수분할

 

본 포스팅은 도서 "문제로 풀어보는 알고리즘"(황인욱, 김용혁 지음)을 공부한 내용을 정리하기 위한 글임을 밝힙니다.

 

 

수분할이란?

 

n 수분할은 자연수 n을 순서에 상관 없이 하나 이상의 자연수의 합으로 나타내는 방법.

예를 들어 3 수분할은 다음 세 가지가 있다.

1+1+1
2+1
3

 

 

순서가 상관 없기 때문에 "1+2"와 "2+1"은 같은 수분할 방법이며, 같은 방법 중에서는 큰 수에서 작은 수의 순서로 적는 방법만 인정하자. 예를 들어서 "1+2+3", "2+3+1"은 이정하지 않고 "3+2+1"만 인정한다. 이렇게 해도 일반성을 잃지 않는다.

 

  5 수분할은 아래와 같이 7 가지이다.

1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
3+2
4+1
5

 

 

 

n/m 수분할이란?

 

더 일반적인 수분할이다. n을 m 이하의 자연수로만 나타내는 방법.

예를 들어 4/1 수분할은 "1+1+1+1" 한 가지가 있고, 3/2 수분할은 "1+1+1", "2+1" 두 가지가 있다.

그렇다면 앞서 설명한 수분할은 n/n 수분할이라고 할 수 있겠다. (n < m 이면, n/m 수분할은 n/n 수분할과 같다.)

 

5/3 수분할은 다은과 같이 다섯 가지이다.

1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
3+2

 

 

 

 

n/m 수분할 프로그램 구현(C언어)

 

n, m을 입력 받아서 n/m 수분할이 모두 몇 가지인지 계산하는 함수를 작성해보자.

 

[실행 예]

input n, m : 5, 3

total : 5

 

 

#include <stdio.h>

#define MAXN 200

/**
 * A function that counts the number of ways that
 * represent 'n' only as natural numbers less than or equal to 'm'
 */
int partition_memo(int n, int m) {
	static int memo[MAXN][MAXN];	// use memoization
	int count = 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++)
		count += partition_memo(n - i, i);
	return memo[n][m] = count;
}

int main(int argc, char** argv) {
	printf("%d\n", partition_memo(20, 10));
	return 0;
}

 

위 코드는 재귀호출을 이용하면서  메모이제이션을 적용하여 중복 계산을 없앤 버전이다.

메모이제이션을 사용하지 않을 경우 partition 계산을 이미 했던 경우도 필요가 생길 때마다 계속해서 새롭게 연산하게 되는데, 메모이제이션을 통해 이를 해결할 수 있다.

 

 

* 참고로, 순서를 생각하는 수분할은 더 간단하다. Pn = 2 ^ (n-1) 이다.