유클리드 호제법(Euclidean-algorithm)- 프로그래머스 : 최대공약수와 최소공배수 [JS]

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

프로그래머스

프로그래머스 : 최대공약수와 최소공배수를 구하는 문제를 풀고 더 나은 풀이법을 공부하기 위해 다른 사람풀이를 살펴봤습니다. 그중 유클리드 호제법이란 개념으로 최대공약수를 푼 풀이에 흥미가 돋아 해당 개념을 블로깅 했습니다. 

기존 푼 풀이

function solution(n, m) {
    var answer =Array(2).fill(1);
    let Max = 1; 
    
    for(let i = 1; i<= Math.min(n,m);i++ ){
        if((n%i===0 )&& (m%i===0)){
            Max = i;
        }
    }
    
    answer[0]= Max; 
    answer[1]= Max*(n/Max)*(m/Max)
    return answer;
}

유클리드 호제법으로 푼 다른 사람 풀이 

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));

유클리드 호제법?

두 수의 최대공약수를 구하는 알고리즘이며, 이 두 수는 어떤 수에 의해 나누어 떨어지는 수 즉 최대공약수 N의 배수라는 점을 이용한 개념입니다. 방식으로 두 값을 나눈 나머지를 계속 구해 나머지가 0이 되었을 때 마지막 계산에서 나누는 수를 최대공약수로 구합니다. 여기서 두 값을 나눈 나머지를 구하는 연산을 MOD 연산이라 하며, MOD 연산을 반복해 나머지가 0이 됐을 때 마지막 계산에서 나누는 수가 두 수의 최대 공약수로 구하게 되는 방식입니다.  

•  유클리드 호제법이란 MOD 연산을 반복해 나머지가 0이 됐을 때 마지막 계산에서 나누는 수로 최대 공약수를 구하는 방식이다.
•  MOD 연산은 두 값을 나눈 나머지를 구하는 연산을 말한다.

이렇게만 말하면 이해 가질 않죠.  1112와 695의 최대공약수를 예시로 풀어봅시다. 이해를 돕기 위해 1112와 695는 최대공약수 139의 배수라는 점을 이미 안 상태에서 살펴봅시다. 1112는 사실 139의 8 배수이며 695는 139의 5 배수입니다.  그래서  1112에서 695를 나눈 나머지  417 또한  결국 최대공약수 139라는 값의 배수입니다.  그래서 점차 나누는 두 수의 값들을 줄이면서   최대공약수를 유추할 수 있고 마지막 나머지가 떨어질 시점에 최대공약수를 구할 수 있습니다. ( 최대공약수 139의 어떤 배수A와 139의 어떤 배수 B를 나누면 나머지 C 또한 139의 어떤 배수이기 때문에 그 나머지 C와 작은 수(B)의 나머지도 작아진 139의 어떤 배수(D)이고 점차 작아지다 결국 최대 공약수 139로 두 수가  나누어 떨어지게 되는 것이죠.)

function greatestNum(a, b) {
  return b ?greatestNum(b, a % b) : a;

}
greatestNum(1112,695);

나머지 417 또한 최대공약수의 배수다

139 가 1112와 695를  나누어 떨어지게 할 수 있는 수 중에 제일 큰 수이다.

출처

https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법(Euclidean-algorithm)