[수학] 유클리드 호제법이란?(gcd, lcm)

유클리드 호제법

알고리즘 문제에서 두 수의 최대 공약수(gcd)를 찾는데 활용되는 알고리즘 이론이다. 

어려운 내용도 아니고 구현도 간단하지만, 그만큼 최대공약수 문제의 기본이 되는 이론이니 익혀두는 것을 추천한다!

원리

두 수 a,b가 있을 때, a를 b로 나눈 나머지를 r이라고 할 때(a%b = r (a>b) ), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 따라서, 이 성질에 따라 a를 b로 나눈 나머지 r을 구한 뒤, b를 r로 나눈 r'를 구하고 r%r' == 0 이 된다면 r'이 a와 b의 최대 공약수가 된다.

(위 같은 식이 성립하는 이유는 나머지 연산(%)이 분배법칙이 성립하기 때문인데, 나머지 연산의 분배법칙 또한 수학 카테고리의 문제의 기본이 되는 경우가 많으니 찾아보길 권장한다.)

예시

81과 36의 최대공약수를 구한다고 생각해보자. 위 유클리드 호제법에 따라 진행하면,

1. 81 % 36 = 9 (81 = 26 *2 +9)

2. 36 % 9 =  0

3. gcd(81,36) = 9

이런 과정을 거쳐 81과 36의 최대공약수는 9라는 것을 알 수 있다!

약수와 배수를 구하는 방법은 여러가지가 있고, 단순히 1부터 모든 약수를 판별하는 방법도 있지만 시간복잡도 측면에서 유클리드 호제법을 활용한다면 훨씬 이득을 챙길 수 있다.

구현

while 문으로 간단히 구현 가능하다. 결국 r % r' == 0 이 되는 r' 값을 찾으면 그 값이 최대 공약수 이다.

public static void main(String args[]){	
    int a, b
    int bignum = Math.max(a, b);
	int smallnum = Math.min(a, b);
		
	while(bignum%smallnum != 0) {
		int r = bignum%smallnum;
		bignum = smallnum;
		smallnum = r;
	}
 }

관련 문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

※참고

알고 있을 것이라 생각하지만, 최소공배수(lcm)는 더 쉽다. a를 최대공약수로 나눈 몫( a/r'), b를 최대 공약수로 나눈 몫(b/r'), 최대공약수 (r')를 곱하면 된다.

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