유클리드 호제법(GCD 구하는 방법)

알고리즘 문제 풀이 도중 두 수의 최대공약수를 구해야하는 과정이 있었다.

원래 사용했던 반복법을 찾아보기 위해 검색하다보니 유클리드 호제법 이라는 키워드를 알게되었고 자세하게 알아보기로 했다.

---

유클리드 호제법

유클리드 호제법(互除法)은 두 개 이상의 양의 정수의 최대공약수를 구하는 방법으로, 유클리드 알고리즘(Euclidean algorithm)이라고 하기도 한다.
[네이버 지식백과] 호제법 (수학백과, 2015.5)

간단히 말해 두 수 a, b의 최대공약수를 구할 때 아래 성질을 이용해 재귀적으로 계산하는 방법을 말한다.

gcd(a, b) = gcd(b, a % b)
(단, b ≠ 0일 때, b = 0이면 결과는 a)

하지만 나의 머리로는 예시가 제대로 이해되지 않았기에 노가다를 이용한 예시를 들어보았다.

예를 들어 gcd(48, 18)을 계산한다면
gcd(48, 18) → gcd(18, 48 % 18) → gcd(18, 12)
gcd(18, 12) → gcd(12, 18 % 12) → gcd(12, 6)
gcd(12, 6) → gcd(6, 12 % 6) → gcd(6, 0)
gcd(6, 0) → 결과는 6

정말 편리한 공식이라는 것은 확실하다.

---

알고리즘에서의 유클리드 호제법의 장점과 단점

장점

1. 두 수의 크기가 커도 시간 복잡도는 O(log N)으로 매우 빠름
2. 재귀 또는 반복문으로 간단하게 구현 가능
3. 수학적으로 안정적이고 검증된 알고리즘
4. LCM(최소공배수), 기하 알고리즘 등 다양한 응용이 가능

단점

1. 값이 매우 클 경우 재귀 호출이 너무 깊어지면 StackOverflow 발생할 위험이 큼
2. 음수값이 들어올 경우 적절히 절댓값 처리해야 함
3. 대규모 계산에서 반복문 방식이 더 안전함

---

유클리드 호제법 활용 예시(프로그래머스 - 멀쩡한 사각형)

public class Test_83_NormalSquare { // 멀쩡한 사각형
    public long solution(int w, int h) {
        long answer = 1;
        // 1.큰 직사각형의 꼭지점을 잇는 대각선으로 자르는 것이므로 최소크기의 대각선 크기를 찾는다.
        // ex) 가로4 * 세로6 크기의 직사각형이 주어진다면 최소 크기는 가로2 * 세로3
        // w와 h의 최대공약수 구하기
        int gcd = gcd(w, h);
        int smallW = w / gcd;
        int smallH = h / gcd;

        // 2. ex) 가로2 * 세로3 에서의 사용할 수 없는 정사각형의 개수를 구하고
        // smallW와 smallH 크기에서의 사용하지 못하는 정사각형의 개수는 항상 smallW + smallH - 1
        long unusableSquare = smallW + smallH - 1;

        // 3. 가로 또는 세로의 크기만큼 배수를 적용하면 총 사용할 수 없는 정사각형의 수를 구할 수 있다.
        answer = (long) w * h - unusableSquare * gcd;

        return answer;
    }

    // 유클리드 호제법으로 최대공약수 구하기
    private int gcd(int w, int h) {
        if (h == 0) {
            return w;
        }
        return gcd(h, w % h);
    }
}