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\)

유클리드 호제법의 원리

유클리드 호제법은 두 수의 최대공약수를 구할 때 가장 널리 쓰이는 방법입니다. 그 핵심은 다음과 같은 성질을 이용하는 것입니다:

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

즉, 큰 수를 작은 수로 나눈 나머지를 이용해 문제를 계속 줄여나가면, 결국 최대공약수에 도달할 수 있다는 원리입니다.

이유는 간단합니다. 어떤 수 \(a\)를 \(b\)로 나누면, 나머지 \(r\)이 존재하고 \(a = bq + r\)의 형태로 쓸 수 있습니다.

이때 \(a\)와 \(b\)의 공통 약수는 \(r\)에도 반드시 공통으로 존재합니다.

따라서 \(a\)와 \(b\)의 최대공약수는 \(b\)와 \(r\)의 최대공약수와 같습니다.

이 과정을 반복하면 나머지가 0이 되는 순간이 오고, 그때의 나누는 수가 바로 최대공약수가 됩니다.

예시

\[\text{GCD}(36, 24) \Rightarrow \text{GCD}(24, 12) \Rightarrow \text{GCD}(12, 0) = 12\]

재귀 함수로 구현하기

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

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\)라고 가정하면, 다음 단계에서 계산되는 나머지 \(r = a \bmod b\) 는 항상 \(0 \leq r < b\) 범위에 있게 됩니다.

즉, 매번 더 작은 수로 문제를 줄여가게 되는 구조입니다.

이 과정은 일반적으로는 매우 빠르게 진행되지만, 예외적으로 느린 경우도 있습니다.

대표적인 예는 피보나치 수열의 인접한 두 항에 대한 경우입니다.

예를 들어 \(F_6 = 8\), \(F_5 = 5\)와 같은 경우우,

\[\text{GCD}(8, 5) \Rightarrow \text{GCD}(5, 3) \Rightarrow \text{GCD}(3, 2) \Rightarrow \text{GCD}(2, 1) \Rightarrow \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이면 서로소 관계입니다. 이 개념은 정수론에서 매우 자주 등장합니다.

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

마무리

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

문제의 크기를 나머지를 통해 줄여가는 구조는 단순하지만 효율적이며, 수학적 원리와 컴퓨터 과학의 효율적인 계산 방식이 어떻게 만날 수 있는지를 잘 보여주는 좋은 예시라고 생각합니다.

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


관련 문제:

이 블로그의 다른 글