문제 개요
서로 다른 원소들로 구성된 배열이 주어졌을 때, 모든 쌍이 서로 나누어 떨어지는 부분 집합, 즉 큰 원소가 항상 작은 원소로 나누어 떨어지는 가장 큰 부분 집합을 찾는 것이 이번 문제의 목표입니다.
입력 : arr[] = {10, 5, 3, 15, 20}
출력 : 3
설명: 가장 큰 부분 집합은 10, 5, 20입니다.
10은 5로 나누어 떨어지고, 20은 10으로 나누어 떨어집니다.
입력 : arr[] = {18, 1, 3, 6, 13, 17}
출력 : 4
설명: 가장 큰 부분 집합은 18, 1, 3, 6입니다.
부분 수열에서 3은 1로, 6은 3으로, 18은 6으로 각각 나누어 떨어집니다.이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 지금부터 그 풀이 방법을 단계별로 살펴보겠습니다.
해결 방법
먼저 배열을 오름차순으로 정렬합니다. 그다음 배열의 끝에서부터 앞쪽으로 순회하면서 dp 배열을 관리하는데, 여기에는 i번째 원소가 해당 부분 집합에서 가장 작은 원소일 때 만들 수 있는 가장 큰 부분 집합의 크기가 저장됩니다. 마지막으로 dp 배열 전체에서 최댓값을 반환하면 정답을 얻을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int largestSubsetPair(int *a, int n){
int dp[n]; // i번째 인덱스에서 시작하는 가장 큰 부분 집합의 크기를 저장
dp[n - 1] = 1; // 마지막 원소가 가장 크므로 부분 집합 크기는 1
int largest = 0; // 정답
for (int i = n - 2; i >= 0; i--) {
int maxi = 0; // 최댓값 초기화
for (int j = i + 1; j < n; j++)
if (a[j] % a[i] == 0 || a[i] % a[j] == 0)
maxi = max(maxi, dp[j]); // a[j]가 a[i]로 나누어 떨어지면
//a[j]를 포함하는 부분 집합의 원소들도 조건을 만족함
dp[i] = 1 + maxi;
largest = max(largest, dp[i]);
}
return largest;
}
int main(){
int a[] = { 1, 3, 6, 13, 17, 18 }; // 주어진 배열
int n = sizeof(a) / sizeof(int); // 배열의 크기
cout << largestSubsetPair(a, n) << "\n";
return 0;
}
실행 결과
4
코드 상세 설명
이 접근 방식은 동적 계획법을 기반으로 문제를 해결합니다. 우선 배열을 오름차순으로 정렬한 뒤, 지금까지 계산된 가장 큰 부분 집합들의 정보를 담아 둘 dp 배열을 준비합니다.
탐색은 배열의 끝에서 시작해 역방향으로 진행됩니다. 현재 원소를 부분 집합의 최솟값이라고 가정하고, 인덱스가 더 큰 원소들 중에서 현재 원소의 배수가 되는 값을 찾습니다. 역방향으로 탐색하고 있기 때문에 해당 원소들의 dp 값, 즉 각 원소를 최솟값으로 하는 가장 큰 부분 집합의 크기는 이미 계산되어 저장된 상태입니다. 따라서 현재 원소의 dp 값에 그 결과를 더해 나가기만 하면 됩니다. 이러한 방식으로 모든 원소를 처리하면 dp 배열의 최댓값이 곧 정답이 됩니다.
시간 복잡도는 정렬에 O(N log N), dp 계산에 O(N²)이 소요되므로 전체적으로 O(N²)입니다. 공간 복잡도는 dp 배열을 위해 O(N)입니다.
마무리
이번 튜토리얼에서는 동적 계획법을 활용해 가장 큰 나눌 수 있는 쌍 부분 집합(Largest Divisible Pairs Subset)을 찾는 문제를 해결했습니다. C++ 구현 코드와 함께 정렬 기반의 전체 풀이 과정도 자세히 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.