프로그래머스) 최대공약수와 최소공배수

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

나의 풀이

function solution(n, m) {
    const nDivisorList = [];
    const mDivisorList = [];
    
    for (let i = 1, j = 1; i <= n, j <= m; i++, j++) {
        if (!(n % i)) {
            nDivisorList.push(i);
        }
        if (!(m % j)) {
            mDivisorList.push(j);
        }
    }
    
    const greatCommonFactor = Math.max(...nDivisorList.filter(num => mDivisorList.includes(num)));
    
    const leastCommonMultiple = (n * m) / greatCommonFactor;
    
    return [greatCommonFactor, leastCommonMultiple];
}

두 수의 약수 중 가장 큰 약수를 구하고(최대공약수) 이 수로 나누어 나온 각각의 몫이 서로소이므로,

두 서로소를 곱하면 최소 공배수를 구할 수 있다.

 

다른 사람의 풀이

function greatestCommonDivisor(a, b) {return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);}
function leastCommonMultipleOfTwo(a, b) {return (a * b) / greatestCommonDivisor(a, b);}
function gcdlcm(a, b) {
    return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)];
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(gcdlcm(3,12));

 

이 코드를 통해 유클리드 호제법이라는 알고리즘을 알게 되었다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

주어진 a와 b 중 a > b라고 가정하였을 때,

a를 b로 나누었을 때 나머지 r이 존재한다면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리이다.

이에 따라 나머지가 0이 될 때까지 나누면 그때 나누는 수가 최대 공약수가 된다.

 

이를 재귀 함수로 구하여 코드를 간결하게 작성하셨다.

 

알고리즘을 풀면서 수학적 지식이 중요하다는 것을 느낀다.

앞으로도 이렇게 찾아보면서 꾸준히 하나하나 익혀나가야겠다.