문제 개요
이 문제에서는 하나의 자연수 n이 주어지며, 우리의 과제는 n을 여러 개의 약수(factor)의 곱으로 표현할 수 있는 모든 조합을 출력하는 것입니다. 일반적으로 1과 n 자기 자신은 조합에서 제외합니다.
예제
주제를 더 쉽게 이해하기 위해 예제를 살펴보겠습니다.
입력: 24 출력: 2 2 2 3 2 2 6 2 3 4 2 12 3 8 4 6
위 결과에서 볼 수 있듯이 24는 2×2×2×3, 2×2×6, 2×3×4, 2×12, 3×8, 4×6처럼 다양한 방식으로 약수들의 곱으로 표현될 수 있습니다.
접근 방법: 재귀와 백트래킹
이 문제는 재귀 함수를 사용해 해결할 수 있습니다. 재귀 함수는 숫자의 약수 조합을 한 단계씩 찾아가며, 지금까지 선택한 약수들의 곱이 n을 초과하지 않는 범위에서만 탐색을 이어갑니다. 완성된 모든 조합은 2차원 벡터(vector of vector)에 저장한 뒤 마지막에 한꺼번에 출력합니다.
알고리즘의 핵심 아이디어
재귀 함수는 다음과 같은 정보를 매개변수로 받습니다.
- first: 이번 단계에서 탐색을 시작할 값. 항상 직전에 선택한 약수보다 크거나 같게 유지하여 중복 조합(예: 2 3 4와 4 3 2)이 생기지 않도록 합니다.
- eachFactor: 지금까지 선택한 약수들의 곱. 이 값이 n에 도달하면 하나의 유효한 조합이 완성된 것입니다.
- n: 목표 숫자입니다.
first부터 n-1까지의 수를 순회하면서 n의 약수인 경우에만 현재 조합에 추가하고, 갱신된 곱(eachFactor × i)을 인자로 재귀 호출을 진행합니다. 탐색이 끝나면 pop_back()으로 마지막 약수를 제거하는 백트래킹을 통해 다른 조합도 시도할 수 있습니다.
C++ 구현
아래 코드는 위에서 설명한 솔루션의 전체 구현입니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> factorCombo;
void generateFactorCombinations(int first, int eachFactor, int n, vector<int> factor) {
if (first > n || eachFactor > n)
return;
if (eachFactor == n) {
factorCombo.push_back(factor);
return;
}
for (int i = first; i < n; i++) {
if (i * eachFactor > n)
break;
if (n % i == 0) {
factor.push_back(i);
generateFactorCombinations(i, i * eachFactor, n, factor);
factor.pop_back();
}
}
}
void printCombination() {
for (int i = 0; i < factorCombo.size(); i++) {
for (int j = 0; j < factorCombo[i].size(); j++)
cout << factorCombo[i][j] << "\t";
cout << endl;
}
}
int main() {
int n = 24;
vector<int> singleResultList;
cout << n << "의 모든 약수 조합은 다음과 같습니다:\n";
generateFactorCombinations(2, 1, n, singleResultList);
printCombination();
return 0;
}
실행 결과
24의 모든 약수 조합은 다음과 같습니다: 2 2 2 3 2 2 6 2 3 4 2 12 3 8 4 6
복잡도 분석
n의 약수 개수는 최대 O(√n)개이며, 각 약수를 조합에 포함할지 말지를 선택하는 과정이 반복되므로 최악의 경우 탐색 공간이 지수적으로 커질 수 있습니다. 다만 곱이 n을 초과하는 가지를 조기에 잘라내는 백트래킹 덕분에 실제 탐색 범위는 크게 줄어듭니다. 공간 복잡도는 저장된 조합의 총 개수에 비례합니다.
마무리
재귀와 백트래킹을 활용하면 숫자의 모든 약수 조합을 체계적으로 생성할 수 있습니다. 이 패턴은 '조합의 합(Combination Sum)'과 같은 대표적인 백트래킹 문제에도 그대로 응용되므로, 잘 익혀두면 다양한 알고리즘 문제 해결에 큰 도움이 됩니다.