[알고리즘] 유클리드 알고리즘을 이용하여, 최대공약수, 최소공배수 구하기(gcd, gcm)

임의의 두 수의 최대 공약수와 최소 공배수를 구하는 방법을 생각해 보자.

유클리드 알고리즘을 사용하면 최대 공약수를 매우 빠르고 간편하게 구할 수 있다. 그러나 아래에서 좀 더 일반적인 예를 이용하여

최대 공약수와 최소 공배수의 성질을 알아보려 한다.

먼저, 최대 공약수와 최소 공배수의 예를보면, 두 수를 12, 20 이라 할 때,

12 = 2 * 2 * 3 ,

20 = 2 * 2 * 5,

최대 공약수(gcd) = 4, (공통된 약수는 2 * 2)

최소 공배수(gcm)  = 60 (중복을 제외한 약수 2 * 2 * 3 * 5)

일반적인 약수를 구하는 방법은 위와 같이 소인수분해를 사용하는 것이다

이 문제를 코딩으로 푼다면 일반적으로 아래와 같이 풀 수 있다.

구하는 방법은 최대 공약수의 범위는 두 수 중 작은 수보다 작거나 같기 때문에, 작은 수를 1씩 감소 시키면서 두 수와 나누어 떨어지는 수를 찾으면 된다.

이렇게 하면 간편하게 반복문을 돌며 최대공약수를 구할 수 있다.

또, 최소 공배수는 두 수 보다 크거나 같기 때문에 gcm()와 같이 반복문을 통해 구할 수 있다. 여기서 gcm()의 반복문은 gcd()보다 더 커질 가능성이 높다.

(두 수가 서로소라면 두 수의 곱이되어 큰 수가 된다.)

gcd의 복잡도는 O(m)   [단, m >= n]

gcm의 복잡도는 O(m*n)

최소공배수는 특히 나쁜 복잡도를 갖는다. 이 문제는 최소공배수와 최대공약수의 성질을 이용하면 좀 더 쉽게 구할 수 있다.

두 수를 m, n이라 할 때, 아래의 수식이 항상 성립된다.

m * n = gcd * gcm

두 수는 주어지고 gcm을 O(m) 수준으로 구할 수 있기 때문에 gcd 또한 O(m) 수준으로 구할 수 있게 된다.

이제 유클리드 알고리즘을 소개할 차례다.

다음의 과정을 통해 최대 공약수를 빠르게 찾을 수 있다.

두 수를 m, n이라 할 때,

1. r = m % n     m을 n으로 나눈 나머지를 r이라 할 때,

2. r == 0 ?    r이 0이면 n이 최대 공약수가 된다.

3. r == 0 X   r이 0이 아니라면, m <= n, n <= r 해서 1.로 가서 과정을 반복한다.

이 과정을 통해 빠르고 쉽게 최대공약수를 구할 수 있게 되고, 여전히 가장 효율적인 방법으로 사용되고 있다. 아래는 코드의 예다.

코드가 매우 간결해졌다. 이와 같은 방법으로 최대 공약수와 최소 공배수를 구하면 된다.