유클리드 호제법(Euclidean Algorithm)

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 효율적으로 구하는 알고리즘이다. 고대 그리스 수학자 유클리드(Euclid)의 이름을 따왔으며 큰 수를 작은 수로 나눈 나머지를 반복해서 0이 될 때까지 진행하는 방식으로 동작한다.

핵심 아이디어
GCD(A, B) = GCD(B, A % B) (단, A > B)

동작 원리

1. 두 정수 A, B (A > B)를 준비한다.
2. A를 B로 나눈 나머지 r = A % B를 구한다.
3. 나머지 r이 0이면, 이때의 B가 최대공약수이다.
4. 나머지가 0이 아니면 A ← B, B ← r로 바꾸고 2단계로 돌아간다.

대표 예제

예제	설명
분수 기약화	분수 a/b를 최대공약수로 나눠 기약분수로 만든다.
최소공배수(LCM) 계산	LCM(a, b) = (a * b) / GCD(a, b) 공식을 이용한다.
배열 전체의 GCD	여러 수의 최대공약수도 유클리드 호제법으로 반복 계산 가능

예시

252와 105의 GCD를 구하는 과정

252 ÷ 105 = 2 ... 42    → 252 % 105 = 42
105 ÷ 42  = 2 ... 21    → 105 % 42 = 21
42 ÷ 21   = 2 ... 0     → 42 % 21 = 0

나머지가 0이 되었으므로 최대공약수(GCD)는 21이다.

Java 구현 예시

public class GCDExample {
    // 유클리드 호제법 - 반복문 버전
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b; // 나머지 계산
            a = b;            // 큰 수를 작은 수로 교체
            b = temp;         // 작은 수를 나머지로 교체
        }
        return a;
    }

    // 재귀 버전
    public static int gcdRecursive(int a, int b) {
        return (b == 0) ? a : gcdRecursive(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(252, 105));          // 출력: 21
        System.out.println(gcdRecursive(252, 105)); // 출력: 21
    }
}

반복문과 재귀 버전 모두 O(log(min(a, b)))로 매우 빠르다. LCM(최소공배수)는 A * B / GCD(A, B)로 구할 수 있다.

📝 배운점

이번에 유클리드 호제법을 공부하면서 최대공약수를 단순히 1부터 모든 수를 나누며 찾는 방식(O(N)) 대신 O(log N)으로 빠르게 구할 수 있다는 점을 배웠다. 특히 GCD(A, B) = GCD(B, A % B)라는 수학적 성질 덕분에 큰 수를 반복적으로 줄여 나가며 효율적으로 계산할 수 있다는 것이 인상적이었다.

또한 반복문과 재귀 두 가지 방식 모두 구현이 간단하고 직관적이며 재귀 버전은 수학적 정의와 거의 동일해서 이해하기 쉽다. 이 알고리즘은 코딩 테스트와 실무에서 최대공약수(GCD)와 최소공배수(LCM)를 빠르게 계산할 때 유용하며 RSA 같은 암호학 알고리즘이나 모듈러 연산 기반의 문제에도 확장해서 활용할 수 있다.