2024.03.11 알고리즘

N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

나의 풀이

... 너무나도 길어서 따로 못올리지만

'에리토스테네스의 체'를 활용하여

엄청난 노가다를 통해 문제를 풀었다

 

하지만 유클리드 호제법을 활용하면 더욱 더 쉽게 풀린다고 한다

 

유클리드 호제법

num1과 num2의 최대공약수는 num2와 'num1에서 num2를 나눈 나머지' 의 최대공약수와 같고,
'num1에서 num2를 나눈 나머지'가 0이라면
그 때의 num2가 num1과 num2의 최대공약수

즉.
GCD(num1, num2) = GCD(num2, num1 % num2)
-> num1 % num2 = 0이라면, 그때의 num2가 최대공약수

 

 

접근방법

최대공약수는 유클리드 호제법으로 값을 도출하고

최소공배수는 두 수의 곱을 최대공약수로 나누어주면 된다

 

풀이

// 최대공약수 구하는 함수
const getGCD = (a, b) => {
    if (b === 0) return a;
    return getGCD(b, a % b);
}

// 최소공배수 구하는 함수
const getLCM = (a, b) => a * b / getGCD(a, b);

function solution(arr) {
   return arr.reduce((a, c, i) => {
        if (i === 0) return c;
        
        return getLCM(a, c)
    }, 1);
}