GCD, LCM을 구하는 가장 효율적인 방법(유클리드 호제법)

최대공약수(GCD) 와 최소공배수(LCM)를 구한다면 알아두어야 할 것이 있었다. (문제 풀다보니 자꾸 틀리단다.)

 

특히나, 알고리즘을 통해서 접근할 때는 효율성에 입각해서 이것을 써야하는 경우가 있다.

시간복잡도를 줄여야 하는 경우가 있다.
그경우 사용할 수 있는 것이 바로 유클리드 호제법이다.

이전에 살펴본 바와 같이 GCD와 LCM은 시간복잡도가 각각 O(N)이다. 이미 O(N)도 훌륭하지만..

 

이것을 O(logN)으로 만드는 것이 바로 유클리드 호제법이다. 

 

문송한 관계로 이해하는데 큰 어려움과 궁금증이 있었다. (분명 초중시절 배운걸텐데 1도 기억이 안난다...) 

 

그것을 토대로 문송한 사람이 이해하는 과정에 대해서 포스팅 해본다.

 

최대공약수와 최소공배수에 대한 개념은 아래 포스팅.

[javascript] 최대공약수와 최소공배수

 

 

유클리드 호제법

두 수 A와 B가 있다.

여기서 A를 B로 나눈 나머지를 R이라고 했을 때

 

A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

식으로 표현하자면 다음과 같다.

GCD(A,B) = GCD(B,R)

처음 접했을 땐 이게 뭔소린가 싶었지만, 예시를 보다보면 어렴풋이 이해할 수 있었다.

 

두 수 16와 12가 있다.
16을 12로 나누면 나머지는 4다. (A=16,B=12,R=4)
16과 12의 최대 공약수는 4다.
12와 4의 최대공약수는 4다. 

즉, 이 둘은 일치한다.

 

다른 예시를 들어 보자

두수 15와 9가 있다.
15를 9로 나누면 나머지는 6이다. (A=15, B=9, R=6)
15와 9의 최대공약수는 3이다. 
9와 6의 최대공약수는 3이다.

즉, 이 둘은 일치한다.

 

그러다 보니 발견된 사실 (by 유클리드)

두수 20과 10이 있다.
20을 10로 나누면 나머지는 0이다. (A=20, B=10, R=0)
20과 10의 최대공약수는 10이다. 
10과 0의 최대공약수는 0이다. 

 

이 둘이 일치 하지 않지만 최대 공약수는 이미 구해져 있었다. 

그래서 도출된 결론은 다음과 같다.

 

R이 0일때 최대공약수는 B이다.

 

이를 통해 기발하게 최대공약수를 찾을 수 있다.

 

R이 0이 될때까지 B를 계속 나머지로 나누면 최대공약수가 구해진다. 

let getGCD_byUCLID = (num1, num2) =>{
	//num2가 0이 되는 순간 멈추기 때문에 num2가 0보다 클 동안 계속 돈다. 
	while(num2 > 0){
		//두 수를 나눈 나머지가 r.
		let r = num1 % num2;
		//num1 자리에 num2가 들어가고
		num1 = num2;
		//num2 자리에 r이 들어가서
		num2 = r;
		//이 while문이 계속 돈다. r이 0이되는 순간까지.
    }
    
    //r이 0일 때, num1자리의 수는 최대공약수가 된다. 
    return num1;
}
//시간복잡도 O(logN);

 

이걸 재귀함수를 통해 돌리는 천재님들이 계셨으니.

function getGCD_byGenius(num1, num2){
	//3항 연산자에 재귀함수를 이용했다.
	const gcd = (a,b) => a % b === 0 ? b : gcd(b, a % b);
    // a를 b로 나눈 나머지가 0이 아니야? 그럼 a빼고 b랑 나머지랑 또 돌아.
    // 0되면 b 내놔.    
	// b는 gcd야.    
    return gcd;
}
//시간복잡도 O(logN);

 

이로서 최고의 효율을 뽐내며 최대공배수를 구했다. 

 

 

최대 공약수와 최소공배수와의 관계.

두 수 A와 B의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다. 

말만들어서 이해를 못해 문송하지만 결국 예를 안들면 이해를 못한다.

 

두 수 8과 12가 있다. 
두수의 최대공약수는 4이고,
두 수의 최소공배수는 24이다. 
8*12 = 96
4*24 = 96

 

어?

 

두 수 3과 4가 있다. 
두수의 최대공약수는 1이고,
두 수의 최소공배수는 12이다. 
3*4 = 12
1*12 = 12

 

이 말은 바꾸어 말하면

최대공약수(GCD)를 알아내면 최소공배수(LCM)도 알 수 있고,
최소공배수(LCM)를 알아내면 최대공약수(GCD)도 알아낼 수 있다는 뜻이다. 

 

최대 공약수는 두 수의 곱을 최소공배수로 나눈것과 같고,
GCD = (num1 * num2) / LCM

최소 공배수는 두 수의 곱을 최대공약수로 나눈것과 같다.
LCM = (num1 * num2) / GCD

 

천재님들은... 이 방법을 다시 응용하셨다.

최대공약수와 최소공배수를 O(log N)으로 구하는 가장 심플한 방법.

function getGcdLcm(num1, num2){
    const gcd = (a,b) => a % b === 0 ? b : gcd(b, a % b);
    
    //최대공약수만 구해놓으면 최소공배수는 구한거다.
    const lcm = (a,b) => a * b / gcd(a,b);

	return [gcd(num1,num2), lcm(num1,num2)];
}

//시간복잡도 O(logN);

 

모든 알고리즘 문제에서 최대공약수와 최소공배수가 관련된 내용이 나오면

반드시 이 함수를 쓰는것이 유리하다는 것을.

문송한 나는 천재님들의 산물을 외워야한다. *(아. 이해했어)

 

 

덧, 배우며 떠오른 궁금증과 깨달음 그리고 스스로의 답변 (문송한건지 멍청한건지)

 

1. 꼭 큰수가 A이어야만 하는가 크기비교를 해야하는 것 아닌가?

두 수의 순서는 관련이 없다.

16을 12로 나누면 나머지가 4지만 12를 16으로 나누면 나머지가 12다. (안나눠지니까). 따라서 R은 12가된다.

16와 12의 최대공약수는 4이다. 이경우 순서만 바뀌었을 뿐이지 값은 어차피 동일하다.

(A=16, B=12, R=4)인 경우와 (A=12, B=16, R=12) 인 경우는 결국 같은 실행을 한번 더 하는 꼴이 된다.

시간복잡도에서 O(N)과 O(N+1)은 같은거니까. 순서에 큰 의미는 없다. 

 

2. 3과 4의 경우처럼 0으로 떨어지는 최대공약수가 없으면 어떻게 되는가? 

당연한 이야기지만 모든 수의 최대 공약수는 1이다. (능지문제인가.)

나머지가 1일 때. 그 나머지(1)를 나머지(1)로 나누면 나머지가 0이된다.(1 % 1 = 0)

 

 

유클리드 호제법을 통해 문제를 손쉽게 해결할 수 있었다.

[분수의 덧셈] 최대공약수와 최소공배수로 분수를 더해보자.