July 5, 2021 1 min to read

자바스크립트로 최대공약수,최소공배수 구하기

코딩 테스트 연습

JavaScript에서 최대 공약수 구하기

프로그래머스 ‘멀쩡한 사각형’ 문제를 풀다가 두 수의 최대공약수가 필요함을 알 수 있다.

이 문제의 핵심은 (가로+세로-최대공약수)로 대각선을 지나는 사각형의 개수를 알 수 있다는점!

Javascript에서 두 수의 최대 공약수를 구할 수 있는 방법은 무엇인가? 사실, 1부터 나눠가며 약수를 구하고 그중 공통된 최대의 수를 구하면 되는데… 듣기만 해도 비효율적이다. 그래서 수학적인 방법이 있지 않을까 싶어 찾아본 결과 방법이있었다!

바로 유클리드 호제법을 활용하는 것! 그렇다면 이 공식은 무엇인가..

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

라고 한다. 즉, a>b인 경우 나누어 진다면 b가 최대 공약수고, 만약 아니라면 b를 나머지로 나누고 다시 나누고… 즉, 재귀를 통해 구현하면 된다.

코드는 아래와 같다.

function solution() {
    const gcd=(a,b)=>{
        if(b===0) return a;
        return gcd(b,a%b);
    }
}

JavaScript에서 최소 공배수 구하기

최대 공약수를 구했다면, 최소 공배수를 구하는 방법은 쉽다! 두 수를 곱하고 최대 공약수로 나누면 된다. 코드는 아래와같다.

function solution() {
    const gcd=(a,b)=>{
        if(b===0) return a;
        return gcd(b,a%b);
    }

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

마무리

이번에는 자바스크립트를 통해 최대,최소 공배수를 구하는 방법을 알아보았다. 사실 c++이나 이외의 코드로도 쉽게 변환이 가능한 코드이다. 프로그래머스의 문제를 기울기로 푸는 방법도 발견했는데 왠지 최대 공약수를 이용하는게 더 깔끔하게 느껴졌다. 이런 공식들을 잘 안다면 코딩 테스트에도 유용할지 모르겠다.