유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘

 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다.

우리가 초등학교 때 배웠던 최대공약수 구하는 법은

ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 나눕니다. 2로 나누겠죠. 그럼 2 4 가 되고 이를 또 2로 나누면 1 2 가 되며 이때 마지막으로 더 나누어지는 수가 없으면 지금까지 나눈 수들을 곱한 값이 최대공약수 입니다. 이는 사람머리로는 간단하지만 알고리즘적으로 생각하면 복잡합니다. 이를 타개하기 위해 무려 기원전 유클리드라는 천재가 발명한 것이 유클리드 호제법 입니다.

 

먼저 유클리드 호제법의 원리는 다음과 같습니다.

1980 , 168 의 최대공약수를 구한다면

1980 % 168 = 132 -> 나누어 떨어지지 않습니다. 즉 최대공약수는 168이 아닌것이죠. 그런데 나머지 132과 168의 최대공약수 = 본래 수들의 최대 공약수는 같습니다. 즉 이제 132와 168의 최대공약수를 찾으면 됩니다.

168 % 132 = 36

132 % 36 = 24

36 % 24 = 12

24 % 12 = 0

 

즉 GCD 는 12 입니다. 

 

이를 코드로 만들면 다음과 같습니다.

int gcd(int a, int b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

 

그리고 최소공배수도 간단하게 만들수가 있습니다. a,b 의 최소공배수는 a * b / gcd(a,b) 입니다. 

즉 

 

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

유클리드 호제법의 시간복잡도는 O(logN) 으로 매우 효율적으로 알려져 있습니다.