GCD(최대공약수)와 유클리드 호제법의 원리 - soo:bak

작성일 :

최대공약수(GCD)란?

두 자연수 (a, b)에 대해 공통된 약수 중 가장 큰 값을 최대공약수(Greatest Common Divisor, GCD)라고 합니다.

예를 들어, (a = 24), (b = 36) 이라면:

  • 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
  • 36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
  • 공통 약수: 1, 2, 3, 4, 6, 12 → 가장 큰 값은 12

즉, \(\text{GCD}(24, 36) = 12\)

유클리드 호제법의 원리

유클리드 호제법은 두 정수의 최대공약수(GCD)를 구할 때 사용하는 대표적인 알고리즘입니다.
그 핵심은 다음과 같은 성질에 있습니다:

\[\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)\]

즉, 큰 수를 작은 수로 나눈 나머지를 이용해서 문제를 반복적으로 줄여가며, 결국 최대공약수에 도달하는 방식입니다.

증명

정수 \(a\)와 \(b\)에 대해, 나눗셈의 기본 성질을 다음과 같이 나타낼 수 있습니다:

\[a = bq + r \quad (0 \leq r < b)\]

여기서,

  • \(q\)는 몫,
  • \(r = a \bmod b\)는 나머지입니다.

어떤 수 \(d\)가 \(a\)와 \(b\)의 공약수라고 가정하면:

\[d \mid a \quad \text{and} \quad d \mid b\]

이므로, 다음이 성립합니다:

\[d \mid (a - bq) \Rightarrow d \mid r\]

즉, \(a\)와 \(b\)의 공약수는 \(r\)의 약수이기도 합니다.


반대로, 만약 \(d\)가 \(b\)와 \(r\)의 공약수라면:

\[d \mid b \quad \text{and} \quad d \mid r \Rightarrow d \mid (bq + r) = a\]

따라서:

\[\text{GCD}(a, b) = \text{GCD}(b, r)\]

가 성립합니다.

반복 구조

이 과정을 나머지가 0이 될 때까지 반복하면, 최종적으로 다음과 같은 구조가 됩니다:

\[\begin{aligned} \text{GCD}(a, b) &= \text{GCD}(b, r_1) \\ &= \text{GCD}(r_1, r_2) \\ &= \cdots \\ &= \text{GCD}(r_{n-1}, 0) \\ &= r_{n-1} \end{aligned}\]

이때 나머지가 0이 되기 직전의 수, 즉 \(r_{n-1}\)이 바로 두 수의 최대공약수가 됩니다.

재귀 함수로 구현하기

가장 기본적인 형태는 다음과 같습니다.

1
2
3
4

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
  • 나머지가 0이 될 때까지 계속해서 함수를 호출하며, 호출이 종료되는 시점에 GCD를 얻을 수 있습니다.
  • 수학적으로 정의된 논리를 그대로 코드에 옮긴 형태입니다.

반복문으로 구현하기

반복문으로도 같은 로직을 구현할 수 있습니다.

1
2
3
4
5
6
7
8

int gcd(int a, int b) {
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}
  • 매번 나머지를 구한 뒤, 두 수를 갱신하는 방식으로 진행됩니다.
  • 스택 호출이 없기 때문에 메모리적으로도 안정적입니다.

시간 복잡도

유클리드 호제법은 매우 빠르게 최대공약수를 구할 수 있는 알고리듬입니다.

이 알고리듬의 시간 복잡도는 일반적으로 입력된 수의 자릿수에 비례하며, 다음과 같이 표현됩니다:

\[O(\log \min(a, b))\]

만약, 두 수 \(a\), \(b\)에 대해 \(a > b\)라고 가정하면,

다음 단계에서는 \(a \bmod b\) 값이 새로운 입력으로 사용됩니다.

이때 나머지 \(r\)는 항상 \(0 \leq r < b\) 범위에 있습니다.

즉, 매 단계마다 더 작은 수로 문제가 줄어드는 구조입니다.

따라서, 일반적인 경우에는 매우 빠르게 종료됩니다.

그러나 예외적으로 느리게 줄어드는 경우도 존재합니다.

대표적인 예로는 피보나치 수열의 인접한 항들 사이의 최대공약수를 구하는 경우입니다.

예를 들어 \(F_6 = 8\), \(F_5 = 5\)에 대해 유클리드 호제법을 적용하면 다음과 같습니다:

\[\text{GCD}(8, 5) \\ \text{GCD}(5, 3) \\ \text{GCD}(3, 2) \\ \text{GCD}(2, 1) \\ \text{GCD}(1, 0)\]

이처럼 한 번에 수가 아주 조금씩만 감소하게 됩니다.

이는 피보나치 수열이 다음 항이 이전 두 항의 합으로 구성되는 특성 때문입니다.

즉, 나머지가 항상 바로 전 항이 되기 때문에 계산이 오래 걸리게 되는 것입니다.

하지만 피보나치 수는 항이 커질수록 지수적으로 증가하므로, 이러한 경우에도 전체 연산 횟수는 입력 수의 자릿수에 비례하게 됩니다.

결론적으로, 최악의 경우에도 유클리드 호제법의 시간 복잡도는 여전히 \(O(\log n)\) 수준을 유지합니다.

활용

유클리드 호제법은 다음과 같은 다양한 상황에서 활용됩니다.

  • 최소공배수(LCM) 계산: \(\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}\) 두 수의 곱을 GCD로 나누면 최소공배수를 구할 수 있습니다. 단, 곱셈을 하는 과정에서 정수 오버플로우에 주의해야 합니다.

  • 분수의 기약 형태 만들기: 분자와 분모의 GCD로 나누어 가장 간단한 형태의 분수로 바꿀 수 있습니다.

    참고 : 기약 분수(irreducible fraction)의 알고리듬적 접근 - soo:bak

  • 서로소 판별: 두 수의 GCD가 1이면 서로소 관계입니다. 이 개념은 정수론에서 매우 자주 등장합니다.

  • 모듈러 연산 기반 문제: 확장 유클리드 호제법이나 모듈러 역원 계산의 기반이 됩니다.

마무리

유클리드 호제법은 고대 수학자 유클리드의 정리에서 유래된 알고리듬이지만, 오늘날에도 알고리듬 문제를 풀거나 정수 계산을 할 때 중요하게 사용됩니다.

문제의 크기를 나머지를 통해 줄여가는 구조는 단순하지만 효율적이며,

수학적 원리와 컴퓨터 과학의 효율적인 계산 방식이 어떻게 만날 수 있는지를 잘 보여주는 좋은 예시라고 생각합니다.

단순한 형태의 재귀 호출만으로도 깊이 있는 계산이 가능하다는 점도 인상깊은 부분 같습니다.


관련 문제:

이 블로그의 다른 글