유클리드 호제법(Euclidean Algorithm): 개념, 원리 및 구현

1. 유클리드 호제법이란?

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 가장 효율적이고 오래된 알고리즘 중 하나이다. 고대 그리스의 수학자 유클리드가 그의 저서 『기하학 원론』에서 처음 소개했다.

GCD는 두 수를 모두 나눌 수 있는 가장 큰 수를 의미하며, 유클리드 호제법은 이 값을 반복적인 나머지 계산을 통해 빠르게 구한다.

2. 알고리즘의 원리

유클리드 호제법은 다음과 같은 성질을 이용한다.

두 수 a, b(a > b)의 최대공약수는 gcd(a, b) = gcd(b, a % b)이다.

이 성질을 기반으로, 나머지가 0이 될 때까지 a % b를 반복하여 계산하면 최종적으로 GCD를 얻을 수 있다.

예제

두 수 48과 18의 GCD를 구해보자.

gcd(48, 18)
→ gcd(18, 48 % 18) = gcd(18, 12)
→ gcd(12, 18 % 12) = gcd(12, 6)
→ gcd(6, 12 % 6) = gcd(6, 0)
→ 결과: 6

3. 구현 (Java)

3.1 재귀 방식

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

3.2 반복문 방식

public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

4. 시간 복잡도

유클리드 호제법의 시간 복잡도는 다음과 같다.

• O(log(min(a, b))) → 매우 빠른 알고리즘
• 재귀 깊이는 로그에 비례하며, 일반적인 정수 범위에서는 매우 효율적이다.

5. 활용 사례

• 분수의 기약화
• 최소공배수(LCM) 계산: lcm(a, b) = (a × b) / gcd(a, b)
• 수학 문제 해결(최대공약수 관련)
• RSA와 같은 공개키 암호 시스템
• 수론 기반 알고리즘 설계

6. 결론

유클리드 호제법은 간단하면서도 강력한 수학 알고리즘으로, 최대공약수를 구하는 데 있어 가장 널리 사용되는 방법이다. 재귀 방식이든 반복문 방식이든 구현이 쉽고, 성능도 뛰어나 수학뿐 아니라 프로그래밍에서도 필수적으로 사용되는 알고리즘이다. 다양한 확장 형태를 통해 수론과 암호학 등 고급 분야에서도 핵심적인 역할을 한다.