JavaScript로 여러 숫자의 최소공배수(LCM) 계산하기

문제 개요

임의의 길이를 가진 숫자 배열을 입력받아, 배열에 포함된 모든 숫자의 최소공배수(LCM, Least Common Multiple)를 반환하는 JavaScript 함수를 작성해야 합니다.

이 문제는 한 번에 해결하려 하면 복잡해지기 쉽습니다. 따라서 다음과 같이 세 단계로 나누어 접근하면 깔끔하고 효율적인 코드를 작성할 수 있습니다.

1단계: 두 수의 최대공약수(GCD) 계산

먼저 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 헬퍼 함수를 만듭니다. 유클리드 호제법을 사용하면 재귀 호출만으로 간단하게 구현할 수 있습니다.

2단계: 두 수의 최소공배수(LCM) 계산

1단계에서 만든 GCD 함수를 활용해 두 수의 최소공배수를 구하는 헬퍼 함수를 작성합니다. 두 수 a, b의 LCM은 다음 공식으로 계산할 수 있습니다.

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

3단계: 배열 전체의 LCM 계산

마지막으로 2단계의 함수를 이용해 배열을 처음부터 끝까지 순회하면서, 지금까지 계산한 LCM 값과 다음 요소의 LCM을 반복해서 구하는 방식으로 배열 전체의 LCM을 완성합니다.

예제 코드

위 접근 방식을 구현한 코드는 다음과 같습니다.

const calculateLCM = (...arr) => {
    const gcd2 = (a, b) => {
        // 두 정수의 최대공약수(GCD)
        if(!b) return b===0 ? a : NaN;
        return gcd2(b, a%b);
    };
    const lcm2 = (a, b) => {
        // 두 정수의 최소공배수(LCM)
        return a * b / gcd2(a, b);
    }
    // 정수 목록 전체의 최소공배수(LCM)
    let n = 1;
    for(let i = 0; i < arr.length; ++i){
        n = lcm2(arr[i], n);
    }
    return n;
};
console.log(calculateLCM(12, 18, 7, 15, 20, 24, 28));

동작 원리

초깃값 n을 1로 설정한 뒤, 배열의 각 요소와 현재까지의 LCM을 차례로 결합해 나가는 것이 핵심입니다. 예를 들어 위 예제에서는 12와 18의 LCM인 36에서 시작해, 7과의 LCM인 252, 그다음 15와의 LCM인 1260으로 누적되다가 최종적으로 2520에 도달합니다. 이렇게 하면 배열의 길이가 몇 개든 상관없이 동일한 로직으로 처리할 수 있습니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

2520