이 자습서에서는 고유한 양의 정수 배열이 제공되는 문제에 대해 설명합니다. 모든 쌍에 대해 더 큰 요소가 더 작은 요소로 나뉘도록 가장 큰 부분집합을 찾아야 합니다. 예를 들어 -
Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.
Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1 해결책을 찾기 위한 접근 방식
이 튜토리얼에서 설명할 두 가지 접근 방식이 있습니다.
간단한 접근
간단한 접근 방식으로 재귀를 적용하여 이 문제를 해결할 수 있습니다. 각 요소를 가져와서 하위 집합에 포함해야 하는지 여부를 확인합니다. 첫 번째 요소부터 시작한다고 가정해 보겠습니다. 하위 집합에 포함하거나 첫 번째 요소에 포함하지 않는 두 가지 옵션이 있습니다. 첫 번째 요소를 포함해 보겠습니다. 그런 다음 두 번째 요소가 하위 집합에 포함되려면 하위 문자열의 요소, 즉 첫 번째 요소로 나눌 수 있거나 나눌 수 있어야 합니다. 이것이 우리가 어레이 전체에 걸쳐 진행하는 방법입니다. 따라서 O(2^n)의 시간 복잡도를 생성하는 2^n 가능한 경로가 있습니다. 이 문제를 해결하기 위한 실행 가능한 접근 방식을 살펴보겠습니다.
효율적인 접근
이 문제에서 동적 프로그래밍을 사용하면 효율적인 접근 방식을 적용할 수 있습니다.
-
배열을 정렬하여 올바른 요소로 나눌 수 있는 왼쪽 요소를 가져옵니다. 나눗셈을 한 번 확인해야 합니다.
-
가장 긴 증가 부분 시퀀스, 즉 dp[ ] 배열을 사용하여 i번째 인덱스까지 나눌 수 있는 가장 큰 부분 집합을 저장합니다. 모든 요소가 자체적으로 분할되기 때문에 각 인덱스를 1로 초기화합니다.
-
이제 두 번째 인덱스에서 반복하고 현재 인덱스로 끝나는 최대 나눌 수 있는 부분 집합에 대해 각 요소를 확인합니다. 이러한 방식으로 각 인덱스의 최대 하위 집합을 찾습니다.
-
이제 배열을 탐색하고 모든 요소에 대해 나눌 수 있는 개수가 가장 큰 제수를 찾습니다. 그리고 현재 인덱스의 나눌 수 있는 개수 값을 해당 요소의 나눌 수 있는 개수 + 1로 변경합니다.
예시
위 접근 방식에 대한 C++ 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
// sorting the array to exclude one condition for division.
sort(nums, nums+n);
vector <int> prev_res(n, -1);
// vector to store divisors of all the elements
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index.
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// check If adding that increases the number of elements in subsequence.
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// finding index having a maximum number of subsets.
if(max<dp[i])
max = dp[i];
}
cout << "Largest divisible subset in the array: ";
// printing the maximum subset
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
} 출력
Largest divisible subset in the array: 6 2 1
결론
이 튜토리얼에서 우리는 문제에 대해 논의했습니다. 주어진 배열에서 각 쌍의 정수를 나눌 수 있는 가장 큰 나눌 수 있는 부분집합을 찾아야 합니다. 우리는 기하급수적인 시간 복잡도를 생성하는 재귀의 접근 방식에 대해 논의했기 때문에 동적 프로그래밍 솔루션에 대해 논의했습니다. 우리는 또한 C, Java, Python 등과 같은 프로그래밍 언어로 할 수 있는 이 문제에 대한 C++ 프로그램에 대해 논의했습니다. 이 튜토리얼이 도움이 되기를 바랍니다.