유클리드(+확장) 알고리즘

카테고리 없음2016. 4. 30. 00:01

최대공약수와 최소공배수를 구하는 알고리즘에 대해 소개해보려고 합니다.

사실, 이 알고리즘을 몰라도 최대공약수를 구할 수는 있습니다.

우선, A라는 수와 B라는 수의 소수를 구하고 A의 첫 번째 소수부터 B의 첫 번째 ~ 마지막 소수까지 일일이 비교해서 공통으로 가지는 수를 찾은 후 공통으로 가지는 수 중에서 가장 큰 수... 그게 최대공약수죠.

하지만 위 방법대로 했다간 1,000자리만 넘어가도 값 구하기는 글러먹은 것 같습니다.

이런 글러먹음을 방지하기 위해, 우리는 유클리드 알고리즘을 배워서 써먹어야 합니다.

유클리드 알고리즘

유클리드 알고리즘은 크게 두 단계로 나뉘어 있으며 각각 유클리드, 확장된 유클리드라 부릅니다. 확장된 유클리드는 유클리드 알고리즘에서 정말 확장(extend)만 된 것이기 때문에 우리는 유클리드부터 먼저 해봅시다.

유클리드는 A = (B * q) + r 의 꼴을 이용하는 알고리즘으로 A, B는 입력한 수, q는 몫, r은 나머지를 의미합니다.

56이라는 수와 12라는 수가 있다고 가정합시다.

56 = (12 * q) + r 의 형태를 갖도록 만들기 위해서는 q = 4, r = 8이 대입되어야 합니다.

하지만 아직 끝난 것이 아닙니다. 유클리드는 r = 0일 때까지 알고리즘을 반복하여야 합니다.

즉, 12 = (8 * q) + r을 구해야 하고 이번에는 q = 1, r = 4이 됩니다. 아직도 r != 0 이므로

8 = (4 * q) + r을 구합니다. q = 2, r = 0 이 되고 r = 0이기 때문에 유클리드는 여기서 끝납니다.

바로 전 식(formula)에서 B자리에 있던 4가 최대공약수가 됩니다.

확장된 유클리드 알고리즘

확장된 유클리드 알고리즘은 유클리드에서 변수 s와 t를 추가합니다. 이 때 s와 t는 앞에서 Q가 Q1, Q2 등으로 구분되었듯이 s1, s2, t1, t2로 구분하며 각각의 초기값은 다음과 같습니다.

s와 t를 사용하여 얻는 것은 다음과 같습니다.

- A*s + B*t를 하면 GCD가 나옵니다.

- (s, t)는 하나의 해가 되며 해는 무수히 많을 수 있습니다. 다른 방정식을 통해 조건에 맞는 해를 구할 수 있습니다.

- 합동의 역을 구하는 데 쓰입니다.

하지만 여기서는 단순히 s와 t를 구하고 GCD를 구하는 것을 보는 용도로만 사용할 것입니다.

앞서 사용했던 56과 12를 마저 사용하겠습니다.

확장된 유클리드를 적용하면 위 표처럼 구해주시면 됩니다.

초기값 이후의 s와 t를 구하는 방법은 아래와 같습니다.

구한 s와 t를 이용하여 얻은 최대공약수는 56x(-1) + 12x5 = 4가 됩니다.

지금까지 알아본 유클리드와 확장된 유클리드는 현재까지 가장 진보한 최대공약수 알고리즘이며 필요하면 쉽게 최대공약수를 구할 수 있도록 C언어로 된 알고리즘 소스도 첨부합니다.

유클리드:: 다운로드

확장된 유클리드:: 다운로드

(되도록 PC버전에서 다운받아주세요!)

아메리카노가 그렇게 맛있답니다 여러분