유클리드 호제법은 두 정수의 최대공약수(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)) \)이 됩니다.

유클리드 호제법

여기서 유클리드 호제법을 사용하면 더 빠르게 찾을 수 있습니다. 유클리드 호제법의 기본 원리는 다음과 같습니다.

두 자연수 \( a, b \,\, (a > b) \)에서 \( a \)를 \( b \)로 나눈 나머지가 \( r \)이라면, 다음이 성립한다.

\[ \gcd(a, b) = \gcd(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;
}

파이썬에서 굉장히 간략하게 작성할 수 있습니다. 반복 횟수 자체는 똑같지만 재귀보다 반복문이 조금 더 가볍고 빠르기 때문에 반복문으로 만드는 것을 조금 더 선호하는 편이기는 하지만 그렇게 큰 차이는 없으니 간략한 재귀를 사용해도 괜찮습니다.

시간복잡도

유클리드 알고리즘이 \( n \)번 작동하기 위해서는 입력값이 최소한 피보나치 수 \( F_{n+1}, F_n \)이상이어야 한다는 오일러의 분석이 있습니다. 여기서 큰 \( n \)과 황금비 \( \varphi \)에 대해 피보나치 수열의 값을 다음과 같이 근사할 수 있습니다.

\[ F_n \approx \frac{\varphi^n}{\sqrt 5} \,\,\,\,\text{ where } \varphi \approx 1.618 \]

따라서 입력이 \( N = F_n \)일 때 \( n \)번 실행된다고 생각할 수 있습니다. 따라서

\[ n = \log_\varphi \sqrt 5 N \]

이므로 시간복잡도는 \( \mathcal{O}(\log N) \)가 됨을 보일 수 있습니다.

최소공배수

최대공약수를 찾았으면 최소공배수도 바로 찾을 수 있습니다. 최소공배수와 최대공약수 사이에는 다음 관계가 성립합니다.

\[ \text{lcm}(a, b) = \frac{ab}{\gcd(a, b)} \]

따라서 a * b / g 로 구할 수 있습니다. 다만, C++같은 언어에서는 정수 범위를 벗어날 수 있기 때문에 a / g * b로 구하는 것을 추천합니다.

Euclidean Algorithm

유클리드 호제법

시간복잡도

최소공배수

연습문제