[재귀 알고리즘] 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) 이다.
'Algorithm' 카테고리의 다른 글
[백준 2579번] 계단 오르기 - JAVA (0) | 2019.05.09 |
---|---|
[C언어] 최대 연속부분수열의 합 (0) | 2019.02.24 |
[동적 프로그래밍 예제] 부분집합의 합(C언어) (1) | 2019.01.17 |
[재귀 알고리즘] 그레이 코드(Gray Code) (0) | 2019.01.15 |
AVL Tree 알고리즘 (0) | 2018.10.29 |