알고리즘 - 유클리드 호제법 (두 수의 최대 공약수 구하기)

 

유클리드 호제법이란, 두 숫자가 주어졌을 때 최대 공약수를 간단하게 구하는 알고리즘이다.

 

일반적으로 두 수의 최대공약수를 구하기 위해선, 두 수를 1부터 차례대로 나누어 가며 두 숫자 모두 나머지가 0이 나오는 숫자를 구해야 한다.

 

숫자의 값이 N, M 이고, N < M 이라고 했을 때, 시간복잡도는 O(N)이 된다.

반면, 유클리드 호제법을 사용하게 되면 O(logN)의 시간 복잡도로 최대 공약수를 구할 수 있다.

 

 

 

유클리드 호제법

---

 

그렇다면, 유클리드 호제법은 어떻게 사용하는 것일까?

 

먼저 코드를 보자.

int GetGCD(int _A, int _B)
{
    int Remain = 0;
    
    while(_B > 0)
    {
    	Remain = A % B;
        A = B;
        B = Remain;
    }
    
    return A;
}

 

위와 같이 매우 짧은 코드이다.

A를 B로 나눈 나머지가 0이 될 때까지 반복문을 돌리면 된다.

 

R이 A % B이고, GCD(A, B)가 A와 B의 최대 공약수라고 했을 때,

GCD(A, B)  = GCD(B, R) 이 성립한다.

 

R1 = B % R이라고 한다면,

GCD(B, R) = GCD(R, R1)또한 성립하는 것이다.

 

반복문을 계속 실행하여, GCD(N, 0)이 될 때 까지 반복한다.

GCD(N,0)의 값은 N이므로, GCD(A,B) = N 이라는 결론이 난다.

 

즉, 위의 코드에서 보면 Remain이 0이 될 때의 A가 GCD가 되는 것이다.

 

아마, 왜 이렇게 되는지는 수학적 증명과정을 거치지 않으면 이해하기 힘들 것이다.

아래는 이해를 돕기 위한 수학적 증명 과정이다.

 

다만, 증명 과정을 꼭 알아야하는 것은 아니다. 오히려 이해를 더 어렵게 만들 수도 있다.

그러니, 관심이 없다면 증명과정은 그냥 스킵하고 위의 공식만 가져다 사용해도 사실 문제는 없다.

 

수학적 증명

먼저, R = A & B 일 때, GCD(A, B) == GCD(B, R)인 이유

 

최대 공약수를 G라고 할 때, 

A = aG;

B = bG; 로 표현할 수 있다. (a와 b는 서로소이다.)

 

q = A / B라고 했을 때,

A = qB + R; 로 표현할 수도 있다.

 

A = qB + R; 

aG = q * bG + R;

aG - q * bG = R;

(a - qb)G  = R;

 

이렇게, R = (a - qb)G 라는 식을 유도할 수 있다.

 처음에 정의했듯, B = bG 이다.

 

R = (a - qb)G 

B = bG 

 

두 수 모두 G라는 공약수를 보유하고 있다.

여기서 a-qb와 b가 서로소라면, G는 최대공약수라고 할 수 있다.

 

이번엔, a-qb와 b가 서로소임을 증명해보겠다.

귀류법을 이용해 증명하도록 하겠다.

 

귀류법이란, 해당 명제가 틀렸음을 가정한 상태에서 모순을 찾는 방식이다.

명제가 틀렸다고 가정했는데 모순이 발생한다면, 반대로 해당 명제는 틀리지 않았음을 증명할 수 있는 것이다.

 

a-qb와 b가 c라는 공약수를 보유하였다고 가정해보자. (단, c는 2이상의 정수이다.)

 

a-qb = Xc;

b = Yc;

 

a - q * Yc = Xc;

a = (X + qY)c;

 

여기서, a = (X + qY)c; 라는 식을 도출하였다.

 

a = (X + qY)c; 가 성립하는 동시에 b = Yc; 도 성립해야 한다.

두 식을 보면 a와 b는 c라는 공약수를 보유하고 있다.

 

그런데, 맨 처음의 가정을 보면 a와 b는 서로소라고 가정을 하였다.

즉, a-qb와 b가 c라는 공약수를 보유하였다는 명제는 모순이 되는 것이다.

그러므로, a-qb와 b는 서로소이다.

 

a-qb과 b가 서로소이므로, 

R = (a - qb)G 

B = bG 

이 두 식에서, R과 B는 G라는 최대공약수를 보유하고 있음을 알 수 있다.

 

G는 A와 B의 최대 공약수이자, B와 R의 최대공약수이다.

-> GCD(A, B) == GCD(B, R)

 

이번엔, GCD(N, 0) 이 N인 이유를 증명해보겠다.

---

GCD(N, 0) 이 N인 이유

 

1. N을 나눌 수 있는 최대 약수는 N이다.

 

2. 나누어 떨어진다는 것은 나머지가 0임을 의미한다.

-> 0은 모든 정수에 대해 나머지가 0이다.

-> 0은 모든 정수로 나누어 떨어진다.

-> 모든 정수는 0의 약수이다.

 

3. N을 나눌 수 있는 최대 약수 = N이며, N은 0의 약수이다..

-> GCD(N, 0)은 N이다.

 

이 유클리드 호제법을 사용하여 최소 공배수(LCM)또한 쉽게 구할 수 있다.

이건 증명과정이 어렵지 않으므로 간단히 참고하도록 해보자.

 

A와 B의 최소 공배수를 L이라고 해보자.

L은 A로도 나누어지고, B로도 나누어지는 수 중에서 최소인 수이다.

즉 A = aG, B = bG라고 했을 때 L = a * b * G; 라고 할 수 있다. (a, b는 서로소이며 G는 A와 B의 최대 공약수)

 

A * B = a * b * G * G

A * B / G = a * b * G = L

 

즉, L 은 A와 B의 곱을 A와 B의 최대 공약수로 나눈 수이다.

int GetLCM(int _A, int _B)
{
    int GCD = GetGCD(_A, _B);
    return (_A * _B) / GCD;
}

 

이렇게 사용하면 된다. 

매우 간단하다.

 

최소 공배수와 최대 공약수를 이용하여 푸는 문제가 생각보다 자주 나온다.

유클리드 호제법을 아는 것과 모르는 것은 문제 풀이에 생각보다 큰 영향을 미친다.

어려운 알고리즘이 아닌 만큼 반드시 숙지하도록 하자.