C++에서 GCD 없이 배열 전체의 최소공배수(LCM) 구하는 방법

배열 A가 주어졌을 때, GCD(최대공약수) 연산을 사용하지 않고 모든 요소의 LCM(최소공배수)을 구해야 합니다. 예를 들어 배열이 {4, 6, 12, 24, 30}과 같다면, 최소공배수는 120이 됩니다.

알고리즘 개요

두 수 사이의 LCM은 비교적 간단하게 계산할 수 있습니다. 두 수 중 더 큰 값부터 시작하여, 그 값이 두 수 모두로 나누어떨어질 때까지 1씩 증가시키면 됩니다. 이를 의사 코드로 표현하면 다음과 같습니다.

getLCM(a, b) −
begin
   if a > b, then m := a, otherwise m := b
      while true do
         if m is divisible by both a and b, then return m
            m := m + 1
   done
end

배열 전체의 LCM 구하기

위 함수를 활용해 배열의 첫 번째와 두 번째 숫자의 LCM을 먼저 구합니다. 이후 그 결과값과 세 번째 요소의 LCM을 구하고, 이 과정을 마지막 요소까지 반복하면 배열 전체의 최소공배수를 얻을 수 있습니다. 즉, 누적된 LCM 값을 하나씩 새로운 요소와 비교해 나가는 방식입니다.

예제 코드

#include <iostream>
using namespace std;
int getLCM(int a, int b){
   int m;
   m = (a > b) ? a : b;
   while(true){
      if(m % a == 0 && m % b == 0)
      return m;
      m++;
   }
}
int getLCMArray(int arr[], int n){
   int lcm = getLCM(arr[0], arr[1]);
   for(int i = 2; i < n; i++){
      lcm = getLCM(lcm, arr[i]);
   }
   return lcm;
}
int main() {
   int arr[] = {4, 6, 12, 24, 30};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "LCM of array elements: " << getLCMArray(arr, n);
}

실행 결과

LCM of array elements: 120

코드 동작 원리

getLCM 함수: 두 정수 a와 b를 입력받아, 더 큰 값을 초기 후보(m)로 설정합니다. 이후 m이 a와 b 모두로 나누어떨어지는지 확인하고, 나누어떨어지지 않으면 m을 1씩 증가시키며 검사를 반복합니다. 조건을 만족하는 순간의 m이 바로 두 수의 최소공배수입니다.

getLCMArray 함수: 배열의 첫 두 요소로 초기 LCM을 구한 뒤, for문을 통해 세 번째 요소부터 마지막 요소까지 차례대로 기존 LCM과의 최소공배수를 갱신합니다. 최종적으로 반환되는 값이 배열 전체의 LCM입니다.

참고 사항

이 방식은 개념을 이해하기에 직관적이지만, 수의 크기가 커지면 반복 횟수가 많아져 성능이 저하될 수 있습니다. 실무 환경에서는 소인수분해 방식이나 유클리드 호제법 기반의 GCD를 활용하는 것이 더 효율적인 대안이 될 수 있습니다.