[알고리즘] 유클리드 호제법 / 최대공약수

2개의 자연수 or 최대공약수를 구하는 알고리즘 중 하나 

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같음

 

최대공약수를 구하는 일반적 방법 

소인수분해를 통해 두 수의 최대공약수를 구하기 위해서 사용 -> 두 수를 소인수분해 한 후, 공통 소수를 찾음

그러나, 숫자가 커질수록 소인수분해 하기 어려움 

 

MOD연산 

두 값을 나눈 나머지를 구하는 연산 

유클리드 호제법은 MOD연산의 반복

나머지가 0이 되었을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수

1112 mod 695 = 417 

695 mod 417 = 278

417 mod 278 =139

278 mod 139 = 0 

 

 * 두 수에 대한 유클리드 호제법 

1) 두 수 중에서 큰 수를 작은 수로 나눔 

2) 만약 나누고 난 나머지가 0이라면 작은 수가 최대공약수임 

3) 만약 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눔 

4) 3)을 반복해 나머지가 0이 될 때의 수가 두 수의 최대공약수

 

* 호제법 : 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘 

 

* 자바스크립트로 유클리드 호제법 표현

function gcd(a,b) {
	const remainder = a % b; 
    if (remainder === 0 ) return b;
    return gcd(b, remainder);
    }
    // 두 수중에서 큰 수를 작은수로 나눌 때, 위의 코드에서는 해당 과정이 빠져 있음 
    // a가 작은수이고 b가 큰수일 때 remainder 값은 a가 됨 
    // return 시, 둘의 위치가 바꾸니 채로 함수가 재귀적으로 돌아가기 때문에 
    // 큰수 /작은수 구분이 필요 없음

 

관련 문제 

호제법 개념을 이해했다면, 관련된 문제를 한 번 풀어봐도 좋을 것 같다. 

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

프로그래머스

 

작성한 풀이 

function solution(n, m) {
    var answer = [];
    const great = (a, b) => {  
        if (b === 0) return a   
        return great(b, a % b)  
    }
    const least = (a,b) => (a*b) / great(a,b)
    return [great(n,m), least(n,m)]
}