서로 다른 양의 정수로 이루어진 집합이 주어졌을 때, 해당 집합 내 모든 원소 쌍 (Si, Sj)이 Si % Sj == 0 또는 Sj % Si == 0 조건을 만족하도록 하는 가장 큰 부분 집합을 찾는 문제입니다.
예를 들어 입력이 [1, 2, 3]이라면 가능한 답은 [1, 2] 또는 [1, 3]이 될 수 있습니다. 2와 3은 서로 나누어 떨어지지 않으므로 두 숫자를 동시에 포함할 수 없기 때문입니다.
문제 해결 접근 방식
이 문제는 최장 증가 부분 수열(LIS) 알고리즘과 유사한 방식으로 동적 계획법(DP)을 적용해 해결할 수 있습니다. 배열을 먼저 오름차순으로 정렬한 뒤, 각 인덱스마다 '해당 원소로 끝나는 나눌 수 있는 부분 집합의 최대 길이'를 저장하고, 경로 추적용 부모 배열(par)을 함께 관리합니다.
알고리즘 단계
- 결과 배열 ret을 만들고 endPoint := 0, retLen := 1, n := nums의 크기로 초기화합니다.
- n이 0이면 빈 집합을 반환합니다.
- nums 배열을 오름차순으로 정렬합니다.
- 크기 n인 두 배열 len과 par를 생성하고, len은 1로, par는 0으로 초기화합니다.
- i를 1부터 n-1까지 반복합니다.
- par[i] := i로 설정합니다.
- j를 0부터 i-1까지 반복하면서, nums[i] % nums[j] == 0이고 len[j] + 1 > len[i]라면:
- len[i] := len[j] + 1로 갱신합니다.
- par[i] := j로 갱신합니다(경로 추적용).
- 갱신된 len[i] > retLen이라면 retLen := len[i], endPoint := i로 업데이트합니다.
- ret에 nums[endPoint]를 삽입합니다.
- endPoint != par[endPoint]인 동안 endPoint를 par[endPoint]로 이동하며 해당 값을 ret에 삽입합니다.
- ret을 뒤집어서 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
vector <int> ret;
int endPoint = 0;
int retLen = 1;
int n = nums.size();
if(!n) return {};
sort(nums.begin(), nums.end());
vector <int> len(n, 1);
vector <int> par(n, 0);
for(int i = 1; i < n; i++){
par[i] = i;
for(int j = 0; j < i; j++){
if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
len[i] = len[j] + 1;
par[i] = j;
}
}
if(len[i] > retLen){
retLen = len[i];
endPoint = i;
}
}
ret.push_back(nums[endPoint]);
while(endPoint != par[endPoint]){
endPoint = par[endPoint];
ret.push_back(nums[endPoint]);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3};
print_vector(ob.largestDivisibleSubset(v));
}입력
[1,2,3]
출력
[1, 2]
복잡도 분석
배열 정렬에 O(n log n), 이중 반복문을 통한 DP 계산에 O(n²)이 소요되므로 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 len과 par 배열을 위해 O(n)입니다. 정렬 덕분에 어떤 수 nums[i]의 약수 후보는 항상 자신보다 앞쪽에 위치하므로, 단일 방향 탐색만으로 조건 검사를 완료할 수 있다는 점이 이 알고리즘의 핵심입니다.