C++로 주어진 정수의 모든 고유한 분할(파티션) 구하기

이 글에서는 주어진 정수의 모든 고유한 분할(partition)을 구하는 C++ 프로그램을 소개합니다. 분할이란 하나의 정수를 여러 개의 양의 정수 합으로 표현하는 방법을 의미하며, 각 분할을 구성하는 수들을 모두 더하면 원래의 정수가 됩니다. 즉, 양의 정수 n이 주어졌을 때 n을 양의 정수들의 합으로 나타낼 수 있는 서로 다른 모든 방식을 생성하는 것이 이 프로그램의 목표입니다.

예를 들어 정수 4의 분할은 4, 3+1, 2+2, 2+1+1, 1+1+1+1처럼 순서만 다른 조합은 하나로 취급하여 중복 없이 모두 출력됩니다.

알고리즘

시작
    함수 displayAllUniqueParts(int m):
    분할을 저장할 배열 p[m]을 선언한다.
    분할에서 마지막 원소의 인덱스 k를 0으로 설정한다.
    첫 번째 분할은 숫자 자기 자신으로 초기화한다. (p[k] = m)
    현재 분할을 먼저 출력한 뒤 다음 분할을 생성하는 while 루프를 만든다.
    루프는 현재 분할이 모두 1로 이루어졌을 때 종료된다.
    displayArray(p, k + 1); 을 호출하여 현재 분할을 출력한다.
    다음 분할 생성:
    val을 0으로 초기화한다.
    p[]에서 가장 오른쪽에 있는 1이 아닌 값을 찾는다.
    또한 val을 갱신하여 몇 만큼의 값이 추가로 수용 가능한지 파악한다.
    만약 k < 0이라면,
        모든 값이 1이므로 더 이상의 분할이 존재하지 않는다.
        위에서 찾은 p[k]를 감소시키고 val을 조정한다.
    val이 더 크다면,
        내림차순 정렬 규칙이 깨지게 된다.
        val을 크기 p[k] 이하의 여러 값으로 나누어 p[k] 뒤의 위치들에 복사한다.
        남은 val을 다음 위치에 복사하고 위치를 증가시킨다.
끝

예제 코드

#include<iostream>
using namespace std;
void printArr(int p[], int m) {
   for (int i = 0; i < m; i++)
      cout << p[i] << " ";
   cout << endl;
}
void printAllUniqueParts(int m) {
   int p[m];
   int k = 0;
   p[k] = m;
   while (true) {
      printArr(p, k + 1);
      int rem_val = 0;
      while (k >= 0 && p[k] == 1) {
         rem_val += p[k];
         k--;
      }
      if (k < 0)
         return;
         p[k]--;
         rem_val++;
      while (rem_val > p[k]) {
         p[k + 1] = p[k];
         rem_val = rem_val - p[k];
         k++;
      }
      p[k + 1] = rem_val;
      k++;
   }
}
int main() {
   cout << "All Unique Partitions of 3\n";
   printAllUniqueParts(3);
   cout << "\nAll Unique Partitions of 4\n";
   printAllUniqueParts(4);
   cout << "\nAll Unique Partitions of 5\n";
   printAllUniqueParts(5);
   return 0;
}

동작 원리 요약

이 알고리즘은 각 분할을 내림차순으로 유지하면서 사전순(lexicographic order)으로 다음 분할을 생성합니다. 먼저 배열 끝쪽에서 연속된 1들을 모두 제거하여 재사용할 값(rem_val)을 모으고, 그중 하나를 마지막 1이 아닌 원소에 더해준 뒤, 남은 값을 해당 원소보다 작거나 같은 크기로 잘라 뒤쪽에 배치합니다. 이 과정을 반복하면 모든 분할이 빠짐없이, 그리고 중복 없이 생성되며 마지막 분할인 "모든 원소가 1"인 경우에 도달하면 종료됩니다.

출력 결과

All Unique Partitions of 3
3
2 1
1 1 1
All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

정리

이 프로그램은 추가 자료구조나 재귀 호출 없이 단순한 배열과 반복문만으로 정수 분할 문제를 해결합니다. 동적 계획법(DP) 기반 접근보다 메모리 사용량이 적고, 분할을 하나씩 순차적으로 생성하므로 전체 분할 목록을 스트림 형태로 처리해야 하는 상황에서도 유용하게 활용할 수 있습니다.