C++로 배열의 모든 부분 배열 중 최소 LCM과 GCD 구하는 방법

문제 개요

크기가 N인 양의 정수 배열 arr가 주어졌을 때, 가능한 모든 부분 배열(subarray) 중에서 최소 LCM(최소공배수)과 최소 GCD(최대공약수)를 구하는 문제입니다.

예를 들어 배열이 {2, 66, 14, 521}이라면, 최소 LCM은 2이고 최소 GCD는 1입니다.

접근 방법: 그리디(Greedy) 기법

이 문제는 그리디 접근법으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• LCM의 경우: 원소의 개수가 줄어들수록 LCM은 작아지거나 같아집니다. 따라서 가장 작은 LCM은 배열 내 단일 원소 중 최솟값이 됩니다.
• GCD의 경우: 반대로 원소의 개수가 늘어날수록 GCD는 작아지거나 같아집니다. 따라서 최소 GCD는 배열의 모든 원소에 대한 GCD와 같습니다.

즉, LCM은 배열 전체를 순회하며 최솟값을 찾으면 되고, GCD는 모든 원소를 순차적으로 누적하여 GCD를 계산하면 됩니다.

C++ 구현 예제

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

// 배열 전체의 최소 GCD 계산
int minimum_gcd(int arr[], int n) {
    int GCD = 0;
    for (int i = 0; i < n; i++)
        GCD = __gcd(GCD, arr[i]);
    return GCD;
}

// 배열 전체의 최소 LCM 계산 (단일 원소 중 최솟값)
int minimum_lcm(int arr[], int n) {
    int LCM = arr[0];
    for (int i = 1; i < n; i++)
        LCM = min(LCM, arr[i]);
    return LCM;
}

int main() {
    int arr[] = { 2, 66, 14, 521 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "LCM: " << minimum_lcm(arr, n)
         << ", GCD: " << minimum_gcd(arr, n);
}

실행 결과

LCM: 2, GCD: 1

정리

두 함수 모두 배열을 한 번씩만 순회하므로 시간 복잡도는 O(N)입니다. GCD 계산에서 초기값을 0으로 설정한 이유는 __gcd(0, x) = x라는 성질 때문으로, 이를 통해 첫 번째 원소부터 자연스럽게 누적 계산이 시작됩니다. 이처럼 수학적 성질을 활용하면 모든 부분 배열을 일일이 탐색하지 않고도 효율적으로 답을 구할 수 있습니다.