유클리드 호제법은 두 정수의 최대공약수(gcd)를 빠르게 찾는 알고리즘입니다. 우선 직관적으로 GCD를 찾는 과정을 생각해 봅시다. GCD는 두 정수 \( a, b \)를 동시에 나누어 떨어지게 하는 수 중 가장 큰 수이므로, 2부터 \( \min(a, b) \)까지 반복하면서 두 수를 모두 나누어 떨어지게 하는지 확인하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int gcd = 0;
for (int i = 2; i <= min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
break;
}
}
cout << gcd;
}
이 경우 시간복잡도는 \( O(\min(N, M)) \)이 됩니다. 참고로, 더 빠른 방법으로는 1부터 시작하는 것이 아니라 \( \min(a, b) \)부터 시작해서 1까지 내려오면서 찾는 방법이 있습니다. 이 경우 가장 먼저 찾은 수가 최대공약수가 되기 때문에 반복문을 조기에 종료할 수 있습니다. 하지만 여전히 최악의 경우에는 1까지 반복해야 하기 때문에 시간복잡도는 동일합니다.
유클리드 호제법
여기서 유클리드 호제법을 사용하면 더 빠르게 찾을 수 있습니다. 유클리드 호제법의 기본 원리는 다음과 같습니다.
두 자연수 \( a, b \,\, (a > b) \)에서 \( a \)를 \( b \)로 나눈 나머지가 \( r \)이라면, 다음이 성립한다.
이때 \( r = 0 \)이라면 최대공약수는 \( b \)가 된다.
증명은 따로 하지 않겠습니다. 이런 방식으로 계속 나머지를 구해 가면서 최대공약수를 찾을 수 있습니다. 하나씩 반복하며 찾지 않아도 되기 때문에 훨씬 빠릅니다.
이걸 이제 코드로 작성하면 다음과 같습니다.
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
굉장히 짧게 끝났네요. 위 조건에서 \( a > b \) 조건이 있었는데, 만약 \( a < b \) 였다면 a % b가 a가 되기 때문에 gcd(b, a)가 실행되어 알아서 swap 되기 때문에 신경쓰지 않아도 됩니다. 재귀를 사용하지 않고도 while을 사용해 해결할 수도 있습니다.
int gcd(int a, int b) {
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
파이썬에서 굉장히 간략하게 작성할 수 있습니다. 반복 횟수 자체는 똑같지만 재귀보다 반복문이 조금 더 가볍고 빠르기 때문에 반복문으로 만드는 것을 조금 더 선호하는 편이기는 하지만 엄청난 차이는 없으니 간단한 문제에서는 편한 방법을 사용하면 됩니다.
시간복잡도
유클리드 호제법이 가장 천천히 작동할 떄는 두 수가 연속된 피보나치 수일 때입니다. 예를 들어, \( a = F_{k + 1}, b = F_k \) 라고 하면 다음과 같이 진행됩니다.
이때 반복 횟수는 \( k \)가 되며, 피보나치 수는 다음과 같이 근사할 수 있습니다.
여기서 \( \phi = \frac{1 + \sqrt{5}}{2} \approx 1.618 \)는 황금비입니다. 따라서 \( k \)에 관해 정리하면,
따라서 유클리드 호제법의 시간복잡도는 \( O(\log \min(a, b)) \)가 됩니다.
최소공배수
최대공약수를 찾았으면 최소공배수도 바로 찾을 수 있습니다. 최소공배수와 최대공약수 사이에는 다음 관계가 성립합니다.
따라서 a * b / g 로 구할 수 있습니다. 다만, C++같은 언어에서는 정수 범위를 벗어날 수 있기 때문에 a / g * b로 구하는 것을 추천합니다.