유클리드 호제법 알아보기

알고리즘 관련 포스팅을 시작하며 첫번째로 알아볼 알고리즘은 유클리드 호제법이다.
기원전 300년경에 쓰인 원론에 나와있는 이 알고리즘은 가장 오래된 알고리즘으로 유명하다. 가장 오래되었으나 가장 심플하고 멋진 알고리즘이다. (역시 옛날사람들이 똑똑하다)

두 수가 주어지고 두 수의 최대공약수(greates common divisor, GCD)를 구하는 알고리즘이며 이를 이용하여 최소공배수(lowest common multiple, LCM) 또한 구할 수 있다.

최대공약수 구하기

간단한 예시를 먼저 들면

154와 42 두 수의 최대공약수를 구하는 방법은
먼저 154와 42를 소인수 분해 하고 그 소인수 분해 된 값들 중 공통된 값들의 곱이 최대공약수가 된다.

154 = 2 * 7 * 11
 42 = 2 * 3 * 7
// (GCD = (2 * 7))

 2 * 7 		= 14
 14 * 11 	= 154
 14 * 3 	= 42

최대 공약수는 14가 되며 154와 42를 각 14로 나눈 몫인 11과 3은 공약수가 없는 서로소가 된다.

위 두 수의 최대공약수를 유클리드 호제법을 통해 구해보면 다음과 같다.

154 % 42 = 28 // 큰 수를 작은수로 나눠 나머지를 구한다. -- 식(1)
 42 % 28 = 14 // 식 (1)에서 작은수를 나머지로 나눈다.  -- 식(2)
 28 % 14 = 0  // 식 (2)를 반복한다. 
 			  // 나머지가 0이 나온다면 앞 식의 나머지가 최대공약수가 된다.

154와 42는 복잡하지 않은 숫자이므로 계산이 비교적 간단하다.
손으로 풀기 겁나는 큰 수의 최대공약수를 구해보자.
78696, 19332

78696 % 19332 = 1368
19332 % 1368  = 180
 1368 % 180   = 108
  180 % 108   = 72
  108 % 72    = 36
   72 % 36    = 0
//두 수의 최대공약수는 36

최대공약수 36이 맞는지 확인해보기 위해서 각 수를 최대공약수로 나눈 수가 서로소인지 확인해보자.

78696 / 36 = 2186        19332 / 36 = 537
//2186과 537이 서로소 인지 확인.

2186 = 2 * 1093
 537 = 3 * 179

2186은 소수 2와 1093으로 이루어져 있으며 537 또한 소수 3과 179로 이루어져 있어 두 수는 서로소가 성립한다.

이 유클리드 호제법을 c언어로 작성해보자.

// 재귀
int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

// 반복문
int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

최소공배수 구하기

이번에는 유클리드 호제법을 이용하여 구한 최대공약수로 최소공배수를 구해보자.

두 수 m, n과 최대공약수 gcd에 대하여 다음이 성립한다.

m = gcd * x
n = gcd * y

우리가 구해볼 최소공배수 lcm은 각 수를 소인수분해하고 중복된 인자를 제거한 후 남은 인자들의 곱이므로 다음 식을 통해 구할 수 있다.

lcm = gcd * x * y
    = gcd * (m / gcd) * (n / gcd)
    = m * n / gcd