알고리즘 공부/알고리즘 이론

유클리드 호제법

EJH 2025. 7. 28. 22:10
반응형

유클리드 호제법(Euclidean Algorithm)

유클리드 호제법은 두 수의 최대공약수(GCD)를 효율적으로 구하는 알고리즘이다. 기원전 300년경 유클리드가 저술한 『기하학 원론』에서 소개된 방법이며, 오랜 시간이 지났지만 여전히 가장 널리 사용되고 있다.

이론 설명

유클리드 호제법은 다음과 같은 성질을 기반으로 한다.

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대공약수와 같다.
즉, GCD(a, b) = GCD(b, a % b)

이 과정을 나머지가 0이 될 때까지 반복하면, 그 마지막 b 값이 최대공약수이다. 이를 간단히 요약하면 다음과 같다.

  1. a를 b로 나눈 나머지 r을 구한다.
  2. a ← b, b ← r로 값을 갱신한다.
  3. b가 0이 될 때까지 위 과정을 반복한다.
  4. 최종적으로 b가 0이 되었을 때의 a 값이 최대공약수이다.

시간 복잡도

유클리드 호제법의 시간 복잡도는 **O(log min(a, b))**이다.
그 이유는 나머지가 반복될수록 수가 급격하게 작아지기 때문이다. 특히 피보나치 수열처럼 최악의 경우에도 로그 시간 내에 수렴한다는 점에서 매우 효율적이다.

공간 복잡도

재귀적으로 구현할 경우, 재귀 깊이만큼 콜 스택을 사용하므로 공간 복잡도는 **O(log min(a, b))**이다.
반면 반복문(while 루프)으로 구현하면 추가적인 메모리 사용이 거의 없기 때문에 **O(1)**의 공간 복잡도를 가진다.

C++ 예제 코드

반복문 기반 구현

#include <iostream>
using namespace std;

int GCD(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a = 48, b = 18;
    cout << "GCD(" << a << ", " << b << ") = " << GCD(a, b) << endl;
    return 0;
}

재귀 기반 구현

#include <iostream>
using namespace std;

int GCD(int a, int b) {
    if (b == 0) return a;
    return GCD(b, a % b);
}

int main() {
    int a = 48, b = 18;
    cout << "GCD(" << a << ", " << b << ") = " << GCD(a, b) << endl;
    return 0;
}

마무리

유클리드 호제법은 단순하지만 매우 강력한 알고리즘이다. 알고리즘 문제 풀이에서 최대공약수를 자주 요구하는 문제는 물론이고, 분수의 기약 형태 계산이나 정수론 전반에서 매우 널리 활용된다. 구현도 간단하고 효율성도 뛰어나므로 꼭 숙지해두는 것이 좋다.

 

반응형