[알고리즘] 유클리드 호제법

유클리드 호제법(-互除法, Euclidean algorithm)

2개의 자연수 또는 정식(整式, 유리식)의 최대공약수를 구하는 알고리즘의 하나이다.

• 호제법: 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

유클리드 호제법은 A와 B의 최대공약수를 A를 B로 나눈 나머지 값을 활용하여 구하는 방식이다. 그 내용은 다음과 같다.

A와 B의 최대공약수를 (A, B)라 표기할 때, (A, B) = (B, A%B) 이다.

유클리드 호제법은 위의 과정을 나누는 수가 0이 되어 더이상 나눌 수 없을 때 까지 반복한다. 수식으로 표현하면 이렇게 된다.

(A, B) = (B, A%B) = (A%B, B%(A%B)) = (B%(A%B), (A%B)%{B%(A%B)}) = ...

예시를 함께 보자.

78696과 19332의 최대공약수를 구하면,
≫ 78696은 19332로 나누어 떨어지지 않기 때문에, 78696을 19332로 나눈 나머지를 구한다.
≫ 19332는 1368로 나누어 떨어지지 않기 때문에, 19332를 1368로 나눈 나머지를 구한다.
≫ 1368는 180로 나누어 떨어지지 않기 때문에, 1368을 180으로 나눈 나머지를 구한다.
≫ ...
≫ 72는 36로 나누어 떨어진다. 나눈 나머지는 0이다. (== 다음 연산에서, 36을 0으로 나눌 수 없다.)
따라서, 최대공약수는 36이다.

설명만 보고서는 이게 무슨 말인지 이해조차 힘들 뿐더러, 이게 도대체 어떻게 가능한 것인가 하는 의문이 든다. 일단 어떤 구조인지 쉽게 파악하기 위해 코드를 가져왔다.

// 1. 반복문
public int GCD(int dividend, int divisor) {
    int mod;
    while(divisor != 0) {
    	mod = dividend % divisor;
        dividend = divisor;
        divisor = mod;
    }
    return dividend;
}

// 2. 재귀
public int GCD(int dividend, int divisor) {
    return (divisor!=0) ? GCD(divisor, dividend % divisor) : dividend;
}

dividend가 나눗셈의 대상이 되고, divisor는 나누는 수가 된다. (A, B) 구조에서 왼쪽이 dividend, 오른쪽이 divisor라고 생각하면 쉽다.

두 수 A와 B의 최대공약수를 찾기 위해 (A>B) A가 dividend, B가 divisor가 되어 모듈러 연산을 반복하는데, 다음 연산에서는 divisor가 dividend가 되고, dividend % divisor의 결과값이 divisor가 되는 것이다. 만약 어느 순간 divisor가 0이 된다면 그 때의 dividend가 최대공약수가 되는 것이다.

근데 이게 어떻게 가능한 것일까? 증명 해보자.

 

유클리드 호제법 증명

위의 증명처럼 b와 (a-bq)는 서로소이기 때문에, B와 A%B의 최대공약수 역시 d가 된다. 유클리드 호제법은 이러한 원리로 동작하는 것이다.