C++로 서로소(Co-prime) 배열 만들기: 최소 삽입 횟수 구하기

이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. N개의 원소를 가진 배열이 주어졌을 때, 이 배열을 서로소(co-prime) 배열로 만들기 위해 필요한 최소 삽입 횟수를 구하는 것이 목표입니다. 여기서 서로소 배열이란, 인접한 두 원소의 최대공약수(GCD)가 항상 1이 되는 배열을 의미합니다. 계산 결과뿐만 아니라 완성된 배열도 함께 출력해야 합니다.

문제 이해하기

예를 들어 {5, 10, 20}이라는 배열을 생각해 봅시다. gcd(5, 10) = 5, gcd(10, 20) = 10이므로 이 배열은 서로소 배열이 아닙니다. 그러나 5와 10 사이, 그리고 10과 20 사이에 각각 1을 삽입하면 어떻게 될까요? 결과 배열은 {5, 1, 10, 1, 20}이 되고, 모든 인접한 쌍의 GCD가 1이므로 서로소 배열이 완성됩니다.

여기서 핵심 아이디어는 간단합니다. 어떤 수 x와 1의 최대공약수는 항상 1이므로, GCD가 1이 아닌 인접한 두 원소 사이에 1을 하나만 삽입하면 해당 위치의 문제가 해결됩니다. 따라서 배열을 한 번 순회하면서 조건을 만족하지 않는 지점마다 1을 삽입하면 되고, 이것이 곧 최소 삽입 횟수가 됩니다.

알고리즘

makeCoPrime(arr, n):
시작
    count := 0
    // 1단계: 삽입이 필요한 지점 개수 세기
    for i in range 1 to n-1 do
        if gcd(arr[i], arr[i-1]) != 1 then
            count := count + 1
    count 값 출력
    arr[0] 출력
    // 2단계: 필요한 위치에 1을 삽입하며 배열 출력
    for i in range 1 to n-1 do
        if gcd(arr[i], arr[i-1]) != 1 then
            1 출력
        arr[i] 출력
종료

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

int makeCoPrime(int arr[], int n){
    int count = 0;
    // 삽입이 필요한 지점 개수 계산
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            count++;
        }
    }
    cout << "최소 삽입 횟수: " << count << endl;

    // 1을 삽입하면서 결과 배열 출력
    cout << arr[0] << " ";
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            cout << 1 << " ";
        }
        cout << arr[i] << " ";
    }
}

int main() {
    int A[] = {2, 7, 28};
    int n = sizeof(A)/sizeof(A[0]);
    makeCoPrime(A, n);
}

실행 결과

최소 삽입 횟수: 1
2 7 1 28

동작 설명 및 복잡도 분석

입력 배열 {2, 7, 28}의 경우, gcd(2, 7) = 1이지만 gcd(7, 28) = 7이므로 7과 28 사이에 1을 한 번 삽입해야 합니다. 따라서 최소 삽입 횟수는 1이고, 결과 배열은 {2, 7, 1, 28}이 됩니다.

시간 복잡도는 배열을 한 번만 순회하면서 각 단계에서 유클리드 호제법으로 GCD를 계산하므로 O(n · log M)입니다. 여기서 M은 배열 원소의 최댓값입니다. 공간 복잡도는 추가 배열 없이 제자리에서 처리하므로 O(1)입니다.