[알고리즘] 확장된 유클리드 알고리즘 (Extended Euclidean Algorithm) 으로 최대공약수 (GCD) 구하기 (C++로 구현하기)

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

'확장된' 이라는 말이 붙었습니다. 그렇다면 유클리드 알고리즘이란 무엇일까요?

많은 분들이 알고 계신 것처럼, 유클리드 알고리즘은 최대공약수 (GCD) 를 구할 때 사용합니다.

만약 375와 275의 최대공약수를 구하고 싶다면 아래와 같이 유클리드 알고리즘을 적용할 것입니다.

 

GCD(375, 275) → 25

 

여기에 덧붙여, 확장된 유클리드 알고리즘은 두 개의 숫자 375, 275에 대해서,

각각에 어떤 값을 곱하고 더해야 최대공약수인 25가 되는지도 알려줍니다.

즉, 아래와 같이 알려준다는 것입니다.

 

xGCD(375, 275) → GCD = 25, S = 3, T = -4

 

여기에서 구해진 S와 T의 값을 이용하면,

 

375 * (3) + 275 * (-4) = 25

 

가 됨을 구할 수 있습니다.

 

이러한 확장된 유클리드 알고리즘은 아래의 경우에 사용됩니다.

 

- 중국인의 나머지 정리

- 디오판토스 방정식

- 합동식 (Congruence Equation) 의 계산

 

 

 

동작 원리

A = 375, B = 275 에 대해서, 확장된 최대공약수를 구해보겠습니다.

가장 먼저 아래와 같이 변수들을 초기화한 후, 테이블을 그립니다.

 

- r1 = A

- r2 = B

- s1 = 1

- s2 = 0

- t1 = 0

- t2 = 1

 

 

그리고 비워져있는 q, r, s, t는 다음과 같이 구합니다.

 

- q = (r1 / r2)

- r = r1 - (q * r2)

- s = s1 - (q * s2)

- t = t1 - (q * t2)

 

 

다음으로, 다음 행의 r1, r2, s1, s2, t1, t2 를 다음과 같이 만들어 나갑니다.

- r1 = 이전 행의 r2

- r2 = 이전 행의 r

- s1 = 이전 행의 s2

- s2 = 이전 행의 s

- t1 = 이전 행의 t2

- t2 = 이전 행의 t

 

 

그 후에는, 위의 과정을 계속해서 반복시켜 나갑니다.

 

 

그러면 최종적으로 위와 같은 테이블이 완성됩니다.

여기에서 빨간색으로 동그라미친 값들은 다음과 같습니다.

- r1 = GCD

- s1 = S

- t1 = T

 

 

 

구현 (C++)

#include <iostream>

using namespace std;

int main(void)
{
	int q, r1, r2, r, s1, s2, s, t1, t2, t;
	int a, b;
	cin >> a >> b;

	r1 = a, r2 = b;
	s1 = 1, s2 = 0, t1 = 0, t2 = 1;

	while (true)
	{
		q = r1 / r2;
		r = r1 - (q * r2);
		s = s1 - (q * s2);
		t = t1 - (q * t2);

		if (r == 0)
		{
			cout << "GCD : " << r2 << '\n';
			cout << "S : " << s2 << '\n';
			cout << "T : " << t2 << '\n';
			break;
		}

		r1 = r2;
		r2 = r;
		s1 = s2;
		s2 = s;
		t1 = t2;
		t2 = t;
	}

	return 0;
}