최대공약수(GCD), 최소공배수(LCM) 알고리즘

1. 최대공약수(Greatest Common Divisor, GCD) & 최소공배수(Least Common Multiple, LCM)

• 최대공약수: 두 수 A와 B의 공통된 약수 중 가장 큰 정수
• 최소공배수: 두 수 이상의 공통된 배수 중 가장 작은 수

 

2. 유클리드 호제법을 이용한 구현

2.1 최대공약수

🌌 원리

a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r)과 같다.
(r이 0인 경우 그 때의 b가 최대공약수이며, a <  b인 경우에는 값이 자동 swap 된다.)

// 재귀함수로 구현
const getGCD = (a, b) => (b > 0 ? getGCD(b, a % b) : a);

// 재귀함수를 사용하지 않은 구현
const getGCD2 = (a, b) => {
  
    while(num2 > 0){
        let r = a % b;
        a = b;
        b = r;
    } 

    return a;
}

 

2.2 최소공배수

: gcd를 이용해서 구함.

🌌 원리

a를 b로 의 최대공약수를 gcd라고 하면 a * b = gcd * lcm 임을 이용한다.
따라서 lcm = gcd * (a/gcd) * (b/gcd)= (a* b) / gcd

const lcm = (a, b) => a * b / gcd(a, b);

 

3. 예제문제

🔒 N개의 최소공배수 구하기 (프로그래머스 연습문제)

🔑 배열에서 처음 수와 다음 수의 최소공배수를 구하고, 그 값 기억하여 다음 수와 최소공배수를 구하는 과정 반복

function solution(arr) {
    let dp = new Array(arr.length);
    dp[0] = arr[0];
    const getGCD = (a, b) => (b > 0 ? getGCD(b, a % b) : a)
    
    for(let i = 1; i < arr.length; i++) {
        dp[i] = dp[i-1] * arr[i] / getGCD(dp[i-1] , arr[i]);
    }
    
    return dp[arr.length-1];
}