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

이번 글에선 유클리드 알고리즘의 진화판, 확장 유클리드 알고리즘(Extended Euclidean Algorithm)에 대해 이해하고, 구현해보자.

 

유클리드 알고리즘은 두 수 a, b의 최대공약수를 구하는 알고리즘이었다. 유클리드 알고리즘을 모른다면 아래 글을 참고하자.

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

 

확장 유클리드 알고리즘이란?

확장 유클리드 알고리즘은 sa + tb = gcd(a, b)를 만족하는 s, t를 구하는 알고리즘이다. 증명은 생략하고, 어떻게 사용하는지 알아보자.

 

두 수 127, 96을 예로 들어보면, 127과 96의 최대 공약수(gcd)는 1이다. 이때

31 * 127  + (-41) * 96 = 3937 - 3936 = 1이며, s = 31, t = -41이 된다.

 

s, t를 어떻게 구할 수 있을까?

확장 유클리드 알고리즘의 원리를 가장 쉽게 설명한 영상은 아래 링크라고 생각한다.

[정수론 7강: 확장된 유클리드 알고리즘 [쑤튜브], 수학채널 쑤튜브, https://youtu.be/PmwLXveLtqc]

 

정수 a를 b로 나눴을 때, 몫을 q, 나머지를 r이라고 한다면

a = bq + r 이 성립한다.

유클리드 알고리즘을 적용하면 이 다음 b를 r로 나누게 되는데, 이때 몫을 q', 나머지를 r'라고 둔다면

b = rq' + r' 가 성립한다.

위 두 식에서 b, r이 겹치는 것을 볼 수 있다. 나눗셈을 반복하면 결국 최대공약수 gcd(a, b)를 구할 수 있게 되고, sa + tb = gcd(a, b)로 표현할 수 있게 될 것이다.

이를 각각 s, t, a / b(= q), a % b(=r)의 표로 표현하면 다음과 같이 쓸 수 있다.

s	t	r
1	0	a
0	1	b
1 - 0(q1) = 1	0 - 1(q1) = -q1	a % b = r1
0 - 1(q2) = -q2	1 - (-q1)(q2) = 1 + q1q2	b % r1 = r2
1 - q2(q3)	-q1 - (1 + q1q2)(q3)	r1 % r2 = r3
...	...	...

표를 잘 들여다보면, 두 개의 s, 두 개의 t를 활용하여 다음 행의 s, t를 구할 수 있음이 보인다. 이후로는 그저 반복일 뿐이므로, 반복문을 사용해 코드로 정리하면 s와 t를 구할 수 있다.

확장 유클리드 알고리즘 구현하기(C++)

// sa + tb = gcd가 되는 s, t를 반환합니다.
std::tuple<int, int> extendedEuclidean(int a, int b) {
	// 초기값과 변수들입니다.
	int s1 = 1, t1 = 0;
	int s2 = 0, t2 = 1;
	int s3 = 0, t3 = 0;
	int q = a / b, r = a % b;

	// r이 0이 되기 전까지 점화 관계를 이용해 s와 t를 구합니다.
	while (r != 0) {
		s3 = s1 - s2 * q;
		t3 = t1 - t2 * q;

		s1 = s2; s2 = s3;
		t1 = t2; t2 = t3;
		a = b; b = r;
		q = a / b; r = a % b;
	}

	// tuple로 s와 t를 반환합니다.
	return std::make_tuple(s3, t3);
}

s, t 두 가지 값을 받아와야 하므로 tuple을 사용해봤다. tuple의 사용법은 생략하겠다.

 

유클리드 알고리즘과 다르게, 확장 유클리드 알고리즘은 s, t의 초기값이 각각 2개씩 정해져 있다. 그렇다면 a가 b보다 작은 경우, 결과가 어떻게 나올까?

int main() {
	std::cout << std::get<0>(extendedEuclidean(127, 96)) << ", " 
		<< std::get<1>(extendedEuclidean(127, 96)) << '\n';
	std::cout << std::get<0>(extendedEuclidean(96, 127)) << ", " 
		<< std::get<1>(extendedEuclidean(96, 127)) << '\n';

	return 0;
}

(127, 96)과 (96, 127)을 넣고 위처럼 돌려보았다.

s, t의 위치가 바꼈다!

처음 예로 들었던 값과 동일하게 나왔다. 두 수의 위치가 바뀐 만큼, s와 t의 위치도 바뀌어 출력되었다.