Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 배열에서 가장 큰 나누어 떨어지는 부분 집합 찾기

문제 개요

이 튜토리얼에서는 서로 다른 양의 정수로 이루어진 배열이 주어졌을 때, 부분 집합 내의 모든 쌍에 대해 큰 수가 작은 수로 나누어 떨어지는 가장 큰 부분 집합을 찾는 문제를 다룹니다. 예를 들면 다음과 같습니다.

입력: nums[ ] = { 1, 4, 2, 6, 7}
출력: 1 2 4
설명:
조건을 만족하는 부분 집합은 (1, 2, 4), (1, 2, 6), (1, 7) 등이 있습니다.
길이가 3인 부분 집합은 2개이며, 각각 모든 쌍이 조건을 충족합니다.

입력: nums[ ] = { 1, 2, 3, 6 }
출력: 6 2 1

해결 접근 방법

이 문제를 해결하는 방법은 크게 두 가지가 있으며, 하나씩 자세히 살펴보겠습니다.

1. 단순한 접근 방식 (재귀)

가장 직관적인 방법은 재귀를 활용하는 것입니다. 각 원소마다 부분 집합에 포함할지 여부를 결정하며 탐색을 진행합니다. 첫 번째 원소부터 시작한다고 가정하면, 해당 원소에는 두 가지 선택지가 있습니다. 부분 집합에 포함하거나, 포함하지 않거나입니다.

첫 번째 원소를 포함했다면, 두 번째 원소가 부분 집합에 추가되려면 기존 부분 집합의 원소로 나누어 떨어지거나 그 원소를 나누어 떨어지게 해야 합니다. 이런 식으로 배열 전체를 순회하게 됩니다.

그러나 이 방식은 각 원소마다 두 가지 경우의 수가 발생하므로 가능한 경로가 2n개가 되어 시간 복잡도가 O(2n)에 달합니다. 입력 크기가 커지면 매우 비효율적이므로, 실용적인 대안을 살펴보겠습니다.

2. 효율적인 접근 방식 (동적 계획법)

동적 계획법(Dynamic Programming)을 적용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 최장 증가 부분 수열(LIS) 알고리즘을 응용하는 것이며, 절차는 다음과 같습니다.

  • 배열 정렬: 배열을 오름차순으로 정렬합니다. 정렬하면 왼쪽 원소가 오른쪽 원소를 나누는지만 확인하면 되므로 나눗셈 검사를 한 번만 수행하면 됩니다.

  • DP 배열 초기화: dp[ ] 배열을 만들어 i번째 인덱스까지의 가장 큰 나누어 떨어지는 부분 집합의 크기를 저장합니다. 모든 원소는 자기 자신으로 나누어 떨어지므로 각 인덱스를 1로 초기화합니다.

  • 순회 및 검사: 두 번째 인덱스부터 시작하여, 현재 인덱스로 끝나는 최대 부분 집합의 크기를 구하기 위해 각 원소를 검사합니다.

  • 값 갱신: 각 원소에 대해 나누어 떨어짐 개수가 가장 큰 약수를 찾고, 현재 인덱스의 값을 '그 원소의 값 + 1'로 갱신합니다.

이 방식의 시간 복잡도는 O(n²), 공간 복잡도는 O(n)으로, 재귀 방식보다 월등히 효율적입니다.

C++ 구현 예제

위 접근 방식을 구현한 C++ 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // 나눗셈 조건 검사를 단순화하기 위해 배열을 정렬
    sort(nums, nums+n);
    // 각 원소의 이전 인덱스(경로 추적용)를 저장하는 벡터
    vector<int> prev_res(n, -1);
    // i번째 인덱스까지의 최대 부분 집합 크기를 저장하는 벡터
    vector<int> dp(n, 1);
    int maxIdx = 0;
    for (int i=1; i<n; i++){  // j번째 인덱스에 i번째 원소의 약수가 있는지 확인
        for (int j=0; j<i; j++){
            if (nums[i]%nums[j] == 0){
                // 해당 원소를 추가하면 부분 수열이 더 길어지는지 확인
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j]+1;
                    prev_res[i] = j;
                }
            }
        }
        // 가장 큰 부분 집합을 가진 인덱스를 찾음
        if(dp[maxIdx]<dp[i])
            maxIdx = i;
    }
    cout << "Largest divisible subset in the array: ";
    // 최대 부분 집합 출력
    int k = maxIdx;
    while (k != -1){
        cout << nums[k] << " ";
        k = prev_res[k];
    }
    return 0;
}

실행 결과

Largest divisible subset in the array: 6 2 1

마무리

이 튜토리얼에서는 주어진 배열에서 모든 쌍의 정수가 서로 나누어 떨어지는 가장 큰 부분 집합을 찾는 문제를 살펴보았습니다. 단순 재귀 방식은 지수 시간 복잡도 O(2n)을 가지므로, 동적 계획법을 활용한 O(n²) 해결 방법을 함께 소개했습니다. 위의 C++ 코드는 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 구현할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되었기를 바랍니다.