[알고리즘👽] js 최대 공약수 유클리드 호제법으로 구하기

해당 포스팅은 유클리드 호제법 알고리즘을 이용해서 자바스크립트 js코드로 최대 공약수를 구하는 알고리즘을 구현합니다. 

최대공약수란?

일단 최대공약수란 무엇일까요? 초등학생때 배워서 아마 대충은 알고 있겠지만 다시 한 번 정리해봅시다!

8의 약수 : 1, 2, 4, 8
10의 약수 : 1, 2, 5, 10
8과 10의 공약수 : 1,2
8과 10의 최대공약수: 2

약수란 어떤 수를 나누어 떨어지게 하는 수입니다. 8의 약수는 1,2,4,8이고 10의 약수는 1,2,5,10입니다. 공약수는 두 수의 공통된 약수입니다. 8과 10의 공약수는 1, 2가됩니다. 그리고 최대공약수는 이 공약수 중에 가장 큰 갑입니다. 8과 10의 최대 공약수는 2가 됩니다.

우리가 초등학생때 배운 최대공약수를 구하는 방법은 두 가지가 있습니다.

1. 나누기 활용하기
2. 지수 이용하기

나누기는 두 수를 동시에 나눠서 나눠지는 값만 골라내고 지수는 소인수분해하고 공통된 소수를 골라냅니다. 방법은 다르지만 결국 공통된 소인수를 찾는 것이 핵심입니다.

유클리드 호제법

코드로 이걸 어떻게 구현할까요? 매번 소인수를 구해서 나눌 수도 있지만 해당 방법은 숫자가 커질 수록 번거롭습니다. 대신 이미 해당 방법을 구현한 알고리즘이 존재합니다. 유클리드 호제법으로 그리스 시대 수학자 유클리드가 만들어낸 인류 최초의 알고리즘입니다.(한국 교육 과정에는 안 나오지만 다른 나라 교육과정에는 포함된다고 합니다.)

A와 B의 최대공약수는 B와 R의 최대공약수와 같다는 성질을 이용합니다. 공식은 간단합니다.

1. 큰 수를 작은 수로 나눈다.
2. 나누는 수를 나머지로 계속 나눈다. 나머지가 0이 나오면 나누는 수가 최대 공약수입니다.

// 24 18
24 % 18 = 6
18 % 6 = 0
24와 18의 최대 공약수 = 6

// 2304 1440
2304 % 1440 = 864
1440 % 864 = 576
864 % 576 = 288
576 % 288 = 0
2304와 1440의 최대공약수는 = 288

위와 같은 방법으로 계속 나누다가 나머지가 0이 나오면 나누는 수를 return하면 됩니다. 이제 코드로 구현하기 쉬워졌네요.

최대 공약수 구하는 코드로 구현하기

while 반복문 사용

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

console.log(gcd(24, 18));

최대공약수는 반복해서 계속 나눠야하므로 반복문을 사용합니다. 나머지가 0인 경우 나누는 수 (b)를 반환합니다. 나머지가 0이 아니라면 a에는 나누는 수(b)를 할당, b에는 나머지를 할당합니다. 이 과정을 나머지가 0이 나올 때까지 반복합니다.

재귀사용

해당 로직을 재귀로도 구현할 수 있습니다. 재귀를 호출할 때 신경 쓸 점은 두 가지가 있습니다.

1. 종료 조건(Base Case)
2. 항상 다른 인자가 들어와야한다. (Diffrent Input)

위에 구현한 최대공약수 함수는 두 조건을 모두 충족합니다. if (나머지 === 0) return b; 라는 종료 조건이 존재하며 a =b, b = 나머지 로 매번 다른 input을 할당합니다.

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

갑자기 식이 짧아졌다고 당황하지마세요. 일단 이전과 종료 조건이 달라졌습니다. 그러나 if(나머지 === 0) 이나 if(b === 0)은 결국 같은 의미입니다. 어차피 나머지는 b에 할당되기 때문입니다. while문에서는 종료 조건을 b>0 으로 설정해서 반복하는 과정을 한 번 줄였습니다. 같은 값이 나오려면 while문은 2번 반복하고 재귀문은 3번 반복합니다.

만약 나머지가 0이 아니라면 a에는 b를 할당하고 b에는 a % b를 할당합니다. 해당 내용이 최대공약수(b, a%b)입니다. 여기까지 왔다면 유클리드 호제법을 완전히 이해한 것입니다.

최소 공배수 구하는 코드 구하기

 

최대공약수의 짝꿍이 존재합니다. 바로 최소공배수입니다. 공통된 약수가 아닌 배수를 찾습니다. 최소 공배수는 최대공약수 값과 나머지 값을 모두 곱하면 됩니다. 즉 두 값을 곱하고 최대공약수 값으로 나누면 최소공배수 값이 나옵니다.

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

해당 특징을 이용해서 로직을 짜면 이렇게 간단하게 값이 나옵니다.

마치면서

최대공약수 최소공배수를 자바스트립트로 구하는 방법을 유클리드 호제법으로 구현해봤습니다. 백준 2609번 문제를 풀면서 정리한 내용으로 어렵지는 않지만 답이 정해진 문제라 기억해두는 것이 좋을 것 같습니다.