모든 부분 집합의 GCD가 주어진 집합에 포함되는 배열 생성하기

이번 글에서는 흥미로운 알고리즘 문제 하나를 살펴보겠습니다. N개의 원소로 이루어진 집합이 주어졌을 때, 생성된 배열의 임의의 부분 집합에 대한 GCD(최대공약수)가 항상 주어진 원소 집합 안에 존재하도록 배열을 만들어야 합니다. 추가 제약 조건으로, 생성된 배열의 길이는 GCD 집합 길이의 3배를 초과하지 않아야 합니다.

예를 들어, {2, 4, 6, 12}라는 4개의 숫자가 주어진 경우, 조건을 만족하는 배열 중 하나는 다음과 같습니다.

{2, 2, 4, 2, 6, 2, 12}

문제 해결 접근 방식

이 문제를 풀려면 먼저 리스트를 오름차순으로 정렬해야 합니다. 그다음 전체 배열의 GCD를 계산했을 때, 이 값이 주어진 집합의 최솟값과 같은지 확인합니다.

• GCD가 최솟값과 같다면 → 각 원소 사이마다 최솟값(=GCD)을 삽입하여 배열을 구성합니다.
• 그렇지 않다면 → 조건을 만족하는 배열을 만들 수 없습니다.

동작 원리

정렬된 배열의 최솟값이 전체 배열의 GCD와 일치한다는 것은, 모든 원소가 최솟값의 배수라는 의미입니다. 따라서 임의의 부분 집합을 선택하더라도 그 부분 집합의 GCD는 반드시 최솟값의 약수이면서 동시에 집합 내 어떤 원소의 약수가 되므로, 항상 집합에 포함됩니다. 각 원소 앞에 GCD를 배치하면 배열 길이는 2n−1로, 3n 이하 제약 조건도 자연스럽게 충족합니다.

알고리즘

generateArray(arr, n)

Begin
    answer := 빈 배열
    gcd := 배열 arr의 전체 GCD
    if gcd == arr의 최솟값 then
        for arr의 각 원소 e에 대해 do
            answer에 gcd 추가
            answer에 e 추가
        done
        answer 출력
    else
        배열을 생성할 수 없음을 출력
    end if
End

C++ 구현 예제

#include<iostream>
#include<vector>
#include<set>
using namespace std;

// 두 수의 최대공약수를 재귀적으로 계산
int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

// 배열 전체의 GCD 계산
int getGCDofArray(vector<int> arr) {
    int result = arr[0];
    for (int i = 1; i < arr.size(); i++)
        result = gcd(arr[i], result);
    return result;
}

// 조건을 만족하는 배열 생성
void generateArray(vector<int> arr) {
    vector<int> answer;
    int GCD_of_array = getGCDofArray(arr);

    if (GCD_of_array == arr[0]) { // GCD가 최솟값과 같은 경우
        answer.push_back(arr[0]);
        for (int i = 1; i < arr.size(); i++) {
            // 각 원소 앞에 최솟값(GCD) 삽입
            answer.push_back(arr[0]);
            answer.push_back(arr[i]);
        }
        for (int i = 0; i < answer.size(); i++)
            cout << answer[i] << " ";
    }
    else
        cout << "No array can be build"; // 배열 생성 불가
}

int main() {
    int n = 4;
    int data[] = {2, 4, 6, 12};
    set<int> GCD(data, data + n); // set을 사용해 자동 정렬
    vector<int> arr;
    set<int>::iterator it;
    for (it = GCD.begin(); it != GCD.end(); ++it)
        arr.push_back(*it);
    generateArray(arr);
}

실행 결과

2 2 4 2 6 2 12

결과 분석

출력 결과를 보면 입력 {2, 4, 6, 12}에 대해 {2, 2, 4, 2, 6, 2, 12}가 생성되었습니다. 이 배열에서 어떤 부분 집합을 골라 GCD를 계산해도 결과는 항상 {2, 4, 6, 12} 중 하나가 됩니다. 예를 들어 {4, 6}의 GCD는 2, {6, 12}의 GCD는 6, {2, 4}의 GCD는 2로 모두 집합에 속합니다. 또한 배열의 길이 7은 원소 개수 4의 3배인 12보다 작으므로 길이 제약 조건도 만족합니다.

복잡도 분석

• 시간 복잡도: GCD 계산에 O(n log M)(M은 최댓값), 배열 생성에 O(n) → 전체적으로 O(n log M)
• 공간 복잡도: 결과 배열 저장에 O(n)