</>sillysillyman
♾️알고리즘

GCD - 유클리드 호제법

GCD를 구하는 가장 오래된 알고리즘. 정의, 구현, 시간 복잡도, 그리고 증명까지.

sillysillyman··4분 읽기

유클리드 호제법이란

“In mathematics, the Euclidean algorithm, or Euclid's algorithm,
is an efficient method for computing the greatest common divisor (GCD) of two integers,
the largest number that divides them both without a remainder.”
(번역) 수학에서, 유클리드 호제법 또는 _유클리드 알고리즘_은 두 정수의 최대공약수, 즉 나머지 없이 두 정수를 나누는 가장 큰 수를 계산하는 효율적인 방법이다.
핵심 아이디어는 하나다.
두 양의 정수 a,b  (a>b)a, b\;(a > b)에 대하여 a=bq+r  (0≤r<b)a=bq+r\;(0\leq r<b)이라 하면,
aa와 bb의 최대공약수는 bb와 rr의 최대공약수와 같다.
gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)
r=0r=0이라면, aa와 bb의 최대공약수는 이다.
큰 수를 나머지로 줄여가며 재귀적으로 반복하면, 나머지가 00이 되는 순간의 bb가 원래 두 수의 최대공약수다.

구현

재귀함수

c++
int gcd(int a, int b) {
	  return b ? gcd(b, a % b) : a;
	}
한 줄짜리 코드지만 호제법의 정의가 그대로 담겨 있다.
  • b ? ... : a → r=0r=0이라면, 최대공약수는 bb이다.
  • gcd(b, a % b) → gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)

반복문

재귀 호출 없이 동일하게 구현할 수 있다.
c++
int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
a %= b로 나머지를 구하고, swap으로 역할을 교체하는 것을 반복한다. b가 0이 되는 순간 a가 최대공약수다.

표준 라이브러리 <numeric>

C++14부터는 <numeric> 헤더에 std::gcd가 제공되므로 직접 구현하지 않아도 된다.
c++
#include <iostream>
#include <numeric>

using namespace std;

int main() {
  cout << gcd(12, 42); // 6
}
참고로, 주요 컴파일러의 std::gcd 구현은 내부적으로 Stein's algorithm(Binary GCD)을 사용한다. 이에 대해서는 추후 다룰 예정이다.

시간 복잡도: O(log⁡min⁡(a,b))O(\log\min(a, b))

결론적으로 유클리드 호제법의 시간 복잡도는 O(log⁡min⁡(a,b))O(\log\min(a, b))다.
나머지 연산을 한 번 수행할 때마다 더 작은 수가 절반 이하로 줄어든다는 것을 보일 수 있다. a≥ba \geq b일 때, a mod b<aba \bmod b < \frac{a}{b}가 항상 성립하기 때문이다.
  • b≤a2b \leq \frac{a}{2}이면, a mod b<b≤a2a \bmod b < b \leq \frac{a}{2}
  • b>a2b > \frac{a}{2}이면, a mod b=a−b<a2a \bmod b = a - b < \frac{a}{2}
두 경우 모두 나머지가 a2\frac{a}{2} 미만이므로, 호출이 두 번 진행될 때마다 인자의 크기가 절반 이하로 줄어든다. 따라서 전체 재귀 깊이(혹은 반복 횟수)는 O(log⁡min⁡(a,b))O(\log \min(a, b))로 수렴한다.

증명 과정

a=bq+r  (0≤r<b)a = bq + r \; (0 \leq r < b)일 때, gcd⁡(a,b)=G\gcd(a, b) = G, gcd⁡(b,r)=G′\gcd(b, r) = G'라 하자.
G=G′G = G'임을 보이면 된다.

GG는 G′G'의 약수다

a=GAa = GA, b=GBb = GB로 나타낼 수 있고, GG는 최대공약수이므로 AA와 BB는 서로소다. a=bq+ra = bq + r에 대입하면 GA=GBq+rGA = GBq + r. 즉, r=G(A−Bq)r = G(A - Bq)다.
GG는 rr의 약수이므로, GG는 bb와 rr 모두의 약수다. gcd⁡(b,r)=G′\gcd(b, r) = G'이므로 GG는 G′G'의 약수다.

G′=GG'=G이다

G′=mGG' = mG라 하면, 서로소인 kk, ll에 대해 다음이 성립한다.
b=GB=G′k=mGk  ⟹  B=mkr=G(A−Bq)=G′l=Gml  ⟹  A=ml+Bq=m(l+kq)b = GB = G'k = mGk \implies B = mk \\ r = G(A - Bq) = G'l = Gml \implies A = ml + Bq = m(l + kq)
즉, mm은 AA와 BB의 공약수다. AA와 BB는 서로소이므로 m=1m=1, 따라서 G′=GG' = G이다.
G=G′G=G'이므로 유클리드 호제법이 성립한다. ■\blacksquare

참고

목록으로