[알고리즘] 최대공약수 빠르게 찾기 - 유클리드 호제법

유클리드 호제법 (Euclidean Algorithm) 이란?

두 개의 자연수의 최대공약수(GCD) 를 빠르게 찾는 알고리즘이다.

유클리드 호제법이 유명한 또 다른 이유는, 이 방법이 인류 최초의 알고리즘이라고 소개되고 있기 때문이다.

최대공약수를 찾는 알고리즘은 여러가지가 있겠지만, 시간복잡도 면에서 가장 훌륭한 알고리즘이기 때문에

PS 과정에서 필요하다면 적극 활용하는 것을 추천한다.

 

 

 

계산 과정

유클리드 호제법은 매우 단순하다.

자연수 A, B가 있다고 가정하고, 다음과 같은 과정을 반복하기만 하면 된다.

 

(1) A를 B로 모듈러 연산한다. (A % B)

(2) 만약 나머지가 0이라면, B가 최대 공약수이다.

(3) 만약 나머지가 0이 아니라면, A를 B로 바꾸고, B를 나머지로 바꾼다.

 

만약 A = 35, B = 14인 예를 생각해보자.

 

35 % 14 = 7

// 나머지가 0이 아니므로, A = 14, B = 7로 바꾼다.

14 % 7 = 0

// 나머지가 0이므로, 현재의 B인 7이 최대공약수이다.

 

 

 

 

시간 복잡도

유클리드 호제법은 O(log (N + M)) 의 시간 복잡도를 가진다.

 

 

 

구현

유클리드 호제법은 재귀를 통해 구현하는 방법과, 반복문을 통해 구현하는 방법이 있다.

 

(1) 재귀를 통한 구현

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

 

 

(2) 반복문을 통한 구현

int gcd_recur(int a, int b)
{
	while (true)
	{
		int c = a % b;
		if (c == 0) return b;
		a = b;
		b = c;
	}
}

 

 

* 시간 차이는 얼마나 날까?

1 ≤ A, B ≤ 10,000

의 범위에서, 재귀와 반복문을 통해서 계산해보면 다음과 같이 반복문이 더 빠르다는 것을 알 수 있다.