[유클리드 알고리즘]최대 공약수, 최소 공배수 구하기

코테를 하면서 가~끔 최대 공약수를 구하는 문제가 나오는데, 이번엔 둘다 구하는 문제였다.

내힘으로 풀었다가 예외 케이스에서 자꾸 틀려서 결국 구글링의 힘을 빌렸다ㅠㅠ...

그런데 잘한듯! 유클리드 알고리즘을 이용하면 쉽게 구할 수 있다

유클리드 알고리즘이란🤔

두 정수의 최대공약수(GCD)를 
효율적으로 계산하기 위해 
고안된 고대 그리스의 방법

 

알고리즘의 기본 원리는 다음과 같다.

기본 원리

1. 정의

• 두 정수 ( a )와 ( b ) (단, ( a > b ))의 최대공약수는 ( b )와 ( a )를 ( b )로 나눈 나머지인 ( r ) (즉, ( r = a \mod b ))의 최대공약수와 같다
• 이를 수식으로 표현하면 다음과 같다

gcd(a,b) = gcd(b,r)

2. 알고리즘의 단계

• 두 수 ( a )와 ( b )를 가지고, ( a )를 ( b )로 나눈 나머지를 구한다.
• 나머지가 0이 되면, ( b )가 최대공약수이다.
• 나머지가 0이 아닐 경우, ( b )와 나머지 ( r )를 가지고 같은 과정을 반복한다.

먼저 쉽게 풀어서 설명한 코드이다. 

function solution(n, m) {
    // 최대공약수를 구하는 함수 정의
    const gcd = (a, b) => {
        // b가 0이면 a가 최대공약수
        if (b === 0) {
            return a;
        }
        // 그렇지 않으면, a를 b로 나눈 나머지를 가지고 재귀 호출
        return gcd(b, a % b);
    };

    // 최소공배수를 구하는 함수 정의
    const lcm = (a, b) => {
        // 최소공배수는 두 수의 곱을 최대공약수로 나눈 값
        return (a * b) / gcd(a, b);
    };

    // 최대공약수와 최소공배수를 배열로 반환
    return [gcd(n, m), lcm(n, m)];
}

// 예시 호출
console.log(solution(3, 12)); // [3, 12]

 

좀더 간략하게 코드를 짠다면 요러케💫

function solution(n, m) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(n, m), lcm(n, m)];
}