[알고리즘] 유클리드 알고리즘 구현하기

유클리드 알고리즘(Euclidean Algorithm)은 유클리드 호제법으로도 불리며, 두 수 a, b의 최대공약수 gcd를 구하는 방법이다. 유클리드 알고리즘의 기본 동작 원리는 간단히 다음과 같이 쓸 수 있다.

 

두 수 a, b가 있을 때, a를 b로 나눈 나머지를 r이라고 하면

1. a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이를 gcd(a, b) = gcd(b, r)과 같이 나타낼 수 있다.

2. gcd(a, 0) = a이다.

 

만약 두 수를 15와 9라고 두자. 그럼 다음과 같이 전개할 수 있다.

gcd(15, 9) = gcd(9, 6) = gcd(6, 3) = gcd(3, 0) = 3

15와 9의 최대공약수인 3을 구할 수 있다.

 

그렇다면 이번에는 위 알고리즘을 코드로 구현해보자. 여기선 C++을 기반으로 작성해보겠다.

1. 반복문으로 구현하기

int gcd(int a, int b) {
	int r;

	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}

	return a;
}

r = a %  b, a = b, b = r을 실행하면 gcd(b, r)과 같아진다. 두번째 인자(b)가 0이 될 때까지 반복하여 최대공약수를 얻을 수 있다.

반복문은 가장 기본적인 방법이지만, 이보다 더 직관적인 방법이 있다.

2. 재귀적으로 구현하기

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

재귀적으로 자기 자신을 호출하는 함수다. gcd(a, b) 호출 시 gcd(b, a % b)을 호출하여 b가 0이 되면 a를 반환한다. (a % b == r)

Q) a가 b보다 작은 경우엔 어떻게 될까?

유클리드 알고리즘을 재귀적으로 구현한 함수를 보면, 두번째 실행엔 a를 b로 나눈 나머지가 들어간다. 그래서 a가 b보다 큰 경우 알고리즘은 제대로 동작한다. 그렇다면 a가 b보다 작은 경우엔 어떻게 될까?

 

a < b인 경우, gcd(a, b)는 gcd(a, a % b)를 호출한다. 이때 a < b이므로 a % b = a가 된다.

즉 gcd(b, a)가 호출되며 둘의 자리가 바뀌며, 큰 수가 왼쪽으로 가게 된다. 그러니 a와 b의 대소는 알고리즘에 영향을 미치지 않는다.

 

 

 

이번 글에서는 두 수의 최대공약수를 얻을 수 있는 유클리드 알고리즘에 대해 알아보았다.

유클리드 알고리즘은 이후 확장 유클리드 알고리즘(Extended Euclidean Algorithm)으로 발전하여, 보안의 기본인 RSA 암호화 알고리즘에 쓰이고 있다. 다음 글에선 확장 유클리드 알고리즘을 구현해보겠다.