수 분할 알고리즘

수 분할 알고리즘.

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

예) 1+1+1

    2+1

3

다만 2+1과 1+2같은 순서만 다른 것은 같은 방법으로 생각한다.

그렇다면 좀 더 일반적인 수분할인 n/m 수분할을 생각해보자.

n을 m 이하의 자연수로만 나타내는 방법을 n/m 수분할이라고 하자.

예)

[5/3 수분할]

1+1+1+1+1

2+1+1+1

2+2+1

3+1+1

3+2

식으로 분할할 수 있다.

따라서 재귀적인 방법을 사용하여 분할하는 수를 줄여나간다면 원하는 개수를 얻을 수 있을 것이다.

재귀적으로 해결한 알고리즘.

int partition(int n, int m){
    int count=0,i;
    if(n<m)
        m=n;
    if(n==0)
        return 1;
    for(i=1; i<=m; i++)
        count += partition(n-i, i);
    return count;
}

재귀적 + 모든 방법을 출력하는 알고리즘.

int partition(int n, int m, int D, int prevNum){
    int count=0, i;
    if(n<m)
        m=n;
    if(n==0)
        return 1;
   
    for(i=1; i<=m; i++){
        if(D==1 && i>1)
            cout<<prevNum<<" ";
        cout<<i<<" ";
        count += partition(n-i, i, D+1, i);
        if(n-i==0){
            cout<<endl;
        }
    }
    return count;
}

[재귀적인 방법 결과]

하지만 일반적인 재귀적인 방법을 이용하여 문제를 해결하고자 한다면, 중복되는 계산때문에 시간

측면에서 비효율적인 알고리즘이 된다.

따라서 중복 계산을 없애는 메모이제이션 방법을 사용할 것이다.

int partition_memo(int n, int m){
    static int memo[MAXN][MAXN];
    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;
};

<!-- 시간 비교--->

재귀적으로 진행하면서, 계산한 값을 배열에 일일히 저장한다. 이후, 다시 그 값을 계산하는 것이

아닌, 배열에서 계산되어진 값을 이용하여 더 높은 값을 구한다.

따라서 훨씬 높은 수를 구할 때는 더 효율적으로 원하는 값을 얻을 수 있다.