JavaScript로 최소공배수(LCM) 구하기

최소공배수(Least Common Multiple, LCM)는 두 개 이상의 수의 공배수 중 가장 작은 수를 말합니다. 프로그래밍에서는 주로 알고리즘 문제나 수학 연산에서 자주 사용되는 개념이죠.

최소공배수의 핵심 공식

최소공배수는 최대공약수(GCD)를 이용하면 간단하게 구할 수 있습니다.

LCM(a, b) = (a × b) / GCD(a, b)

이 공식이 성립하는 이유는 두 수를 곱하면 공통 인수(GCD)가 중복으로 들어가기 때문입니다. 따라서 한 번 나눠주면 정확한 최소공배수가 됩니다.

기본 구현

GCD 함수는 이미 구현되어 있다고 가정하고, LCM 함수를 작성해봅시다.

// GCD 함수 (유클리드 호제법)
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

// LCM 함수
function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

// 사용 예시
console.log(lcm(12, 18));  // 36
console.log(lcm(4, 6));    // 12
console.log(lcm(15, 25));  // 75

오버플로우 방지 버전

큰 수를 다룰 때는 먼저 곱셈을 하면 오버플로우가 발생할 수 있습니다. 이를 방지하기 위해 다음과 같이 순서를 조정할 수 있습니다.

function lcm(a, b) {
  return (a / gcd(a, b)) * b;
}

먼저 a를 GCD로 나눈 후 b를 곱하면 중간 계산값이 작아져서 오버플로우를 방지할 수 있습니다.

여러 개의 수의 LCM 구하기

3개 이상의 수의 최소공배수를 구하려면 reduce 메서드를 활용하면 편리합니다.

function lcmMultiple(...numbers) {
  return numbers.reduce((acc, num) => lcm(acc, num));
}

console.log(lcmMultiple(4, 6, 8));      // 24
console.log(lcmMultiple(3, 5, 7));      // 105
console.log(lcmMultiple(2, 3, 4, 5));   // 60

배열에서 LCM 구하기

배열 형태로 입력을 받는 경우도 많습니다.

function lcmArray(numbers) {
  if (numbers.length === 0) return 0;
  if (numbers.length === 1) return numbers[0];
  
  return numbers.reduce((acc, num) => lcm(acc, num));
}

const nums = [12, 15, 20];
console.log(lcmArray(nums));  // 60

실전 예제: 분수의 덧셈

분수의 덧셈에서 통분할 때 LCM을 사용합니다.

function addFractions(num1, den1, num2, den2) {
  // 분모의 최소공배수를 구함
  const commonDen = lcm(den1, den2);
  
  // 각 분자를 통분
  const newNum1 = num1 * (commonDen / den1);
  const newNum2 = num2 * (commonDen / den2);
  
  // 분자를 더함
  const resultNum = newNum1 + newNum2;
  
  // 기약분수로 만들기
  const divisor = gcd(resultNum, commonDen);
  
  return {
    numerator: resultNum / divisor,
    denominator: commonDen / divisor
  };
}

// 1/4 + 1/6 = 5/12
const result = addFractions(1, 4, 1, 6);
console.log(`${result.numerator}/${result.denominator}`);  // 5/12

실전 예제: 주기 문제

서로 다른 주기를 가진 이벤트가 동시에 발생하는 시점을 찾을 때도 LCM을 사용합니다.

function findNextMeeting(periods) {
  return lcmMultiple(...periods);
}

// A는 3일마다, B는 4일마다, C는 5일마다 회의
// 모두 함께 회의하는 것은 며칠 후?
console.log(findNextMeeting([3, 4, 5]));  // 60일 후

성능 고려사항

LCM의 시간 복잡도는 GCD의 시간 복잡도에 의존합니다. 유클리드 호제법을 사용한 GCD는 O(log min(a, b))의 시간 복잡도를 가지므로, LCM 역시 매우 효율적입니다.

여러 개의 수의 LCM을 구할 때는 O(n log m) 정도의 복잡도를 가집니다. (n은 수의 개수, m은 수의 크기)

마무리

최소공배수는 최대공약수를 알면 간단한 공식으로 쉽게 구할 수 있습니다. 알고리즘 문제나 실무에서 다양하게 활용되니 꼭 익혀두시기 바랍니다!

// 완성된 코드
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

function lcmMultiple(...numbers) {
  return numbers.reduce((acc, num) => lcm(acc, num));
}