[수학응용] 유클리드 호제법(Euclidean algorithm)

유클리드 호제법

최대공약수(Greatest Common Divisor)를 구하는 유클리드 호제법(Euclidean algorithm) 다음 두 명제를 기반으로 한다.

• 첫째, 어떤 두 수가 배수 관계에 있을 때, 두 수 중에서 작은 수는 최대공약수가 된다.

• 둘째, 어떤 두 수의 최대 공약수는 큰 수(피제수 : 나누어지는 수)를 작은 수(제수 : 나누는 수)로 나누었을 때, 그 나머지와 작은 수의 최대공약수와 같다.

예를 들어 A, B라는 두 정수의 최대공약수를 구하는 과정은 다음과 같다.

A와 B는 Q(몫), R(나머지)와 함께 아래와 같이 나타낼 수 있다.

A = Q1*B + R1

여기서 A와 B의 최대공약수는 나머지 R1과 B(제수)의 최대공약수와 같다. 따라서 다시 아래와 같은 식을 만들 수 있다.

B = Q2*R1 + R2

또 다시 A와 B의 최대공약수는 R1과 R2의 최대공약수와 같다. 이 과정을 반복하면서 제수가 나머지로 나누어 떨어지는 때의 제수가 A, B의 최대공약수가 된다. 이 과정을 코드로 나타낼 때 재귀함수를 사용하면 굉장히 간단하게 나타낼 수 있다.

int GCD(int x,int y) { if(!y) return x; else return GCD(y,x%y); }

나머지가 0이 될 때(제수로 나누어 떨어질 때)의 제수를 반환하는 것을 볼 수 있고, 그 값이 최종 GCD함수의(바깥) 리턴값임을 알 수 있다.

그리고 함수에 전달되는 인자들의 위치는 중요하지 않다. 예를 들어 GCD(5, 6)이 수행되는 과정을 보자.

5와 6에서 6이 제수이고 나머지는 5가 된다. 그러면 다시 GCD(6, 5)가 수행되므로 결과값은 동일하다.

최소공배수(Least Common Multiple)

최소공배수를 구하는 방법은 매우 간단하다. 주어진 두 수를 곱하고 최소공배수로 나누어주면 된다.

int LCM(int x,int y) { return x / GCD(x,y) * y; }