유클리드 호제법-최대공약수/최소공배수 구하기

이 글은 유클리드 호제법에 대한 설명과 최대공약수와 최소공배수를 JavaScript로 구현하는 방식에 대해 정리하는 글입니다.

01  유클리드 호제법

유클리드 호제법(Euclidean algorithm)이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

유클리드 호제법 알고리즘의 골자

 

유클리드 호제법의 원리는 다음과 같다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있다.

 

유클리드 호제법을 사용한다면 비교대상의 두 수 a와 b에서 a를 b로 나눈 나머지를 r이라고 했을 때 a % r이 0이 될 때까지 반복을 해주는 방식으로 최대공약수를 산출하기에 시간 복잡도를 O(Log N)으로 줄일 수 있어 좀 더 효율적인 알고리즘을 작성할 수 있다.

 

02  최대공약수 (Greatest Common Divisor, GCD)

공약수(common divisor)란 두 개 이상의 자연수의 공통된 약수이고, 그 중 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다.

 

유클리드 호제법의 원리를 이용해 최대공약수를 구해보자.

큰 수 A가 작은 수 B로 나누어 떨어지면, A, B의 최대공약수는 B이다.
 A를 B로 나누었을 때 나머지가 R이면, A, B의 최대공약수는 R과 B의 최대공약수와 같다.
 :  GCM(A,B) = GCM(B,R) / ex) GCM(15,12) = GCM(12,3)

//반복문
function gcd(a, b) {
    while (b != 0) {
        let r = a % b;
        [a, b] = [b, r];
    }
    return a;
}

//재귀
function gcd(a,b){ 
  if(a%b===0) return b;
  else return gcd(b, a % b);
}

let gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);

03  최소공배수 (Lowest Common Multiple, LCM)

공배수(common multiple)란 두 개 이상의 자연수의 공통된 배수이며, 그 중 최소공배수(LCM)란 두 수 이상의 여러 수의 공배수 중 최소인 수를 가리킨다.

 

최소공배수(LCM) = A x B / 최대공약수(GCD) 이므로 위의 최대공약수 알고리즘으로 최대공약수를 구하고 A x B x GCD 를 구하면 된다.

//(A,B의 최소공배수) = A * B / (A,B의 최대공약수)

//두 수(a,b) 중 어느 한수가 다른 한수의 약수가 아니면
//최소공배수 = 최대공배수 * a * b

function lcm(a,b){
	return a * b / gcd(a,b);
}

let lcm = a * b / gcd(a,b);

04  문제 활용 방식

분수의 덧셈

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/120808

 

최소공배수 활용 문제

function solution(denum1, num1, denum2, num2) {
    var answer = [];
    //분자
    let denum=(denum1*num2)+(denum2*num1);
    //분모
    let num = num1 * num2;
    //최소공배수
    let gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    let min=gcd(denum,num)
    
    answer=[denum/min,num/min]
    
    return answer;
}

최대공약수와 최소공배수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12940

 

최대공약수, 최소공배수 구하는 문제

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

N개의 최소공배수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12953

function solution(arr) {
    var answer = 0;
    answer=arr.reduce((a,b)=>lcd(a,b));
    
    return answer;
}
let lcd = (a,b) => a * b / gcd(a, b);
let gcd = (a,b) => a % b === 0 ? b : gcd(b, a % b);

---

참고자료

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

https://gomcine.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-6-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC