C++로 정수의 모든 인수 조합 구하기

어떤 수를 생각해 봅시다. 하나의 수는 여러 인수(약수)들의 곱으로 표현할 수 있습니다. 예를 들어 8은 2 × 2 × 2로도, 2 × 4로도 표현할 수 있습니다. 이번 문제는 정수 n을 입력받아, n을 두 개 이상의 인수로 분해할 수 있는 모든 조합을 반환하는 함수를 만드는 것입니다.

예를 들어 입력이 12라면, 출력은 [[2, 6], [2, 2, 3], [3, 4]]가 됩니다.

접근 방법

이 문제는 재귀 호출과 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 n을 가장 작은 인수부터 차례대로 나누면서, 남은 몫에 대해 같은 과정을 반복적으로 적용하는 것입니다. 알고리즘을 단계별로 살펴보겠습니다.

solve() 함수를 정의합니다. 이 함수는 n(현재 값), target(원래 입력값), start(탐색을 시작할 최소 인수)를 매개변수로 받습니다.
결과를 저장할 2차원 벡터 ret을 선언합니다.
n이 1이면 더 이상 분해할 수 없으므로 ret을 그대로 반환합니다.
n이 target과 다르다는 것은 n이 이미 부분적인 분해 결과라는 의미입니다. 이 경우 n 자체도 하나의 유효한 조합이므로 ret에 {n}을 추가합니다.
i를 start부터 i * i <= n이 성립하는 동안 1씩 증가시키며 반복합니다. 제곱근까지만 검사하면 불필요한 탐색을 줄일 수 있습니다.
n을 i로 나누었을 때 나머지가 0이라면, solve(n / i, target, i)를 재귀 호출하여 남은 값의 조합들을 얻습니다. 여기서 start 대신 i를 넘겨주면 조합이 오름차순으로 유지되어 중복이 발생하지 않습니다.
반환된 각 조합(other[j])의 끝에 i를 추가하고, 완성된 조합을 ret에 삽입합니다.
모든 반복이 끝나면 ret을 반환합니다.

메인 함수에서는 solve(n, n, 2)를 호출하여 최종 결과를 얻습니다. 시작값을 2로 지정하는 이유는 1을 인수로 사용하면 무한히 많은 조합이 생기기 때문입니다.

C++ 구현 예제

아래 코드를 통해 동작 방식을 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v){
   cout << "[";
   for(int i = 0; i < v.size(); i++){
      cout << "[";
      for(int j = 0; j < v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}

class Solution {
public:
   vector<vector<int>> solve(int n, int target, int start){
      vector<vector<int>> ret;
      if(n == 1){
         return ret;
      }
      if(n != target){
         ret.push_back({n});
      }
      for(int i = start; i * i <= n; i++){
         if(n % i == 0){
            vector<vector<int>> other = solve(n / i, target, i);
            for(int j = 0; j < other.size(); j++){
               other[j].push_back(i);
               ret.push_back(other[j]);
            }
         }
      }
      return ret;
   }
   vector<vector<int>> getFactors(int n) {
      return solve(n, n, 2);
   }
};

int main(){
   Solution ob;
   print_vector(ob.getFactors(16));
}

입력

출력

[[8, 2],[4, 2, 2],[2, 2, 2, 2],[4, 4]]

코드 설명 및 시간 복잡도

입력이 16인 경우를 살펴보겠습니다. 16은 [8, 2], [4, 4], [4, 2, 2], [2, 2, 2, 2]로 분해될 수 있으며, 프로그램은 이 네 가지 조합을 모두 출력합니다.

이 알고리즘의 시간 복잡도는 대략 O(√n · k)입니다. 각 재귀 단계에서 √n까지만 후보 인수를 검사하기 때문에 전체 범위를 탐색하는 것보다 훨씬 효율적입니다. 공간 복잡도는 생성되는 조합의 개수에 비례하며, 재귀 깊이 역시 인수의 개수만큼만 증가합니다.

핵심 포인트를 정리하면 다음과 같습니다.

start 값을 재귀 호출 시 현재 인수 i로 갱신하여 조합의 중복을 방지합니다.
n != target 조건 덕분에 원래 수 자체(예: [16])는 결과에 포함되지 않고, 두 개 이상의 인수로 나뉜 조합만 반환됩니다.
i * i <= n 조건으로 탐색 범위를 제곱근까지만 한정하여 성능을 최적화합니다.