유클리드 호제법으로 최대공약수(GCD) 구하기: C++ 재귀 구현

이 글에서는 두 수의 최대공약수(GCD)를 구하는 유클리드 호제법(Euclidean Algorithm)에 대해 알아보겠습니다. 최대공약수(Greatest Common Divisor)란 두 수를 모두 나누어 떨어지게 하는 가장 큰 정수를 의미하며, 유클리드 호제법을 활용하면 이 값을 매우 간단하고 효율적으로 구할 수 있습니다.

구현 방식은 크게 두 가지가 있습니다. 하나는 반복문(loop)을 사용하는 방식이고, 다른 하나는 재귀 호출(recursion)을 사용하는 방식입니다. 여기서는 코드가 더 간결한 재귀 방식의 유클리드 알고리즘을 사용해 보겠습니다.

유클리드 호제법의 원리

핵심 아이디어는 다음과 같습니다. 두 수 a와 b의 최대공약수는 'b mod a'와 'a'의 최대공약수와 같다는 성질을 이용합니다. 이 과정을 a가 0이 될 때까지 반복하면, 그 시점의 b가 곧 두 수의 최대공약수가 됩니다.

알고리즘

EuclideanAlgorithm(a, b)

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

C++ 예제 코드

#include<iostream>
using namespace std;
int euclideanAlgorithm(int a, int b) {
    if (a == 0)
        return b;
    return euclideanAlgorithm(b%a, a);
}
main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    cout << "GCD " << euclideanAlgorithm(a, b);
}

실행 결과

Enter two numbers: 12 16
GCD 4

동작 과정 살펴보기

입력값이 12와 16일 때의 실행 흐름은 다음과 같습니다.

• euclideanAlgorithm(12, 16) → euclideanAlgorithm(16 mod 12, 12) = euclideanAlgorithm(4, 12)
• euclideanAlgorithm(4, 12) → euclideanAlgorithm(12 mod 4, 4) = euclideanAlgorithm(0, 4)
• a가 0이므로 b인 4를 반환 → 즉, GCD(12, 16) = 4

이처럼 유클리드 호제법은 나머지 연산만으로 최대공약수를 빠르게 구할 수 있는 효율적인 방법입니다. 시간 복잡도는 O(log(min(a, b)))로 매우 우수하여, 실무에서도 널리 활용됩니다.