C++ 배열에서 최대 GCD(최대공약수)를 가진 쌍 찾기

양의 정수로 이루어진 배열이 주어졌을 때, 배열 안의 두 정수로 만들 수 있는 쌍 중 GCD(최대공약수) 값이 가장 큰 쌍을 찾는 것이 이 글의 목표입니다. 예를 들어 A = {1, 2, 3, 4, 5}라면 결과는 2입니다. 쌍 (2, 4)의 GCD가 2이며, 그 외 모든 쌍의 GCD 값은 2보다 작기 때문입니다.

문제 해결 접근 방법

이 문제는 약수 카운트 배열(divisor count array)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 각 원소에 대해 1부터 √arr[i]까지의 수를 확인하며 약수를 찾고, 해당 약수의 등장 횟수를 카운트 배열에 기록합니다. 하나의 약수를 찾으면 짝이 되는 약수(arr[i] / j)도 함께 세어주므로, 약수를 구하는 과정은 원소당 O(√arr[i]) 시간이 걸립니다.

모든 원소에 대한 탐색이 끝나면, 카운트 배열을 가장 큰 인덱스부터 1까지 역순으로 순회합니다. 이때 카운트 값이 1보다 큰 인덱스를 발견하면, 그 수는 최소 두 개 이상의 원소의 공통 약수라는 뜻이며, 역순으로 처음 발견되는 값이 곧 최대 GCD가 됩니다.

예제 코드

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

int getMaxGCD(int arr[], int n) {
    int high = 0;
    // 배열에서 최댓값을 구해 카운트 배열의 크기를 결정
    for (int i = 0; i < n; i++)
        high = max(high, arr[i]);

    // 각 약수의 등장 횟수를 저장하는 배열
    int divisors[high + 1] = { 0 };

    // 각 원소의 약수를 찾아 카운트 증가
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= sqrt(arr[i]); j++) {
            if (arr[i] % j == 0) {
                divisors[j]++;
                if (j != arr[i] / j)
                    divisors[arr[i] / j]++;
            }
        }
    }

    // 큰 값부터 확인하여 두 개 이상의 원소가 공유하는 약수 반환
    for (int i = high; i >= 1; i--)
        if (divisors[i] > 1)
            return i;
}

int main() {
    int arr[] = { 1, 2, 4, 8, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max GCD: " << getMaxGCD(arr, n);
}

실행 결과

Max GCD: 4

위 예제에서 배열 {1, 2, 4, 8, 12}의 경우, 4와 8의 GCD가 4이며 이것이 가능한 최댓값이므로 프로그램은 4를 출력합니다.

시간 복잡도 분석

각 원소의 약수를 구하는 데 O(√M)(M은 원소의 최댓값)의 시간이 소요되므로, 전체 시간 복잡도는 O(N√M)입니다. 또한 최댓값 M에 비례하는 추가 공간이 필요합니다. 이 방법은 모든 쌍을 일일이 비교하는 O(N² log M) 방식보다 훨씬 효율적입니다.