C++ 프로그램: 배열에서 나눌 수 있는 가장 큰 부분 집합 찾기

이 튜토리얼에서는 다양한 양의 정수 배열이 제공되는 문제에 대해 논의합니다. 더 큰 요소의 각 쌍이 더 작은 요소로 나누어지도록 가장 큰 부분 집합을 찾아야 합니다. 예를 들어 -

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&#39;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;
}

Output

Largest divisible subset in the array: 6 2 1

결론

이 튜토리얼에서 문제에 대해 논의했습니다. 주어진 배열에 있는 모든 정수 쌍의 가장 큰 나눗셈 수를 찾아야 합니다. 하위 집합. 기하급수적인 시간 복잡도를 생성하는 재귀적 접근 방식에 대해 논의했기 때문에 동적 프로그래밍 솔루션에 대해서도 논의했습니다. 또한 이 문제를 해결하기 위해 C, Java, Python 등과 같은 프로그래밍 언어를 사용하여 구현할 수 있는 C++ 프로그램에 대해서도 논의했습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 C++ 프로그램: 배열에서 나눌 수 있는 가장 큰 부분 집합 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!