유클리드 호제법(Euclidean algorithm)

유클리드 호제법 (Euclidean algorithm) 

이번에는 유클리드 호제법에 대해 알아보도록 하겠습니다. 먼저 유클리드 호제법이 뭔지 알아보겠습니다. 유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 알고리즘을 공부할 때, 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least Common Multiple)을 구하는 데 유용하게 사용되는 방식 입니다.

 

원리

이름은 거창해보이고 복잡할 것 같지만, 그 원리를 보면 그다지 복잡하지 않습니다. "두 수의 최대공약수는, 큰 수에서 작은 수를 나눈 나머지와 작은 수의 최대공약수와 같다." 라는 원리로 접근하여 값을 도출하는 알고리즘입니다.

 

최대공약수는 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값이고, 최소공배수는 두 자연수들의 배수들 중에서 공통된 가장 작은 수입니다. 이제 공식을 살펴봅시다.

 

두 정수 a와 b (a >= b)의 최대공약수 gcd(a,b)는 위 원리에 따라 gcd(a,b) = gcd(b,a mod b) 공식으로 나타낼 수 있습니다.

mod 연산은 우리가 흔히 아는 나머지 연산(%) 입니다.

 

위 공식을 바탕으로 하나의 예시를 들어 실행해보겠습니다. gcd(24, 18)을 실행하면 나머지 연산을 통해 gcd(18, 6)이 되고 다시 진행하면, gcd(6, 0)이 됩니다. 이후 연산은 나머지가 0이 나오기 때문에 최종적으로 나온 a의 값인 6이 최대공약수입니다. 이를 간단한 C++ 코드로 표현한다면 아래와 같습니다.

 

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        cout << "a: " << a << ", b: " << b << ", a % b: " << r << endl;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a = 24, b = 18;
    int result = gcd(a, b);
    cout << "GCD: " << result << endl;
    return 0;
}

 

GCD의 활용

이제 유클리드 알고리즘에 대해 알았으니 최소공배수(LCM)을 구하는 방법도 알아보겠습니다. 최소공배수는 두 자연수의 곱 / 최대공약수 라는 공식이 적용되므로, 우리가 구한 최대공약수 GCD를 활용할 수 있습니다. 위에 예를 들었던 gcd(24, 18)에서의 최대공약수는 6이고, 최소공배수는 공식에 따라 24 * 18 / 6이 되므로 72가 나오게 됩니다.

 

시간복잡도

유클리드 알고리즘은 기원전 300년경 유클리드의 <원론>에서 처음으로 등장한 아주 오래된 방법이지만, 지금까지도 빠르고 효율적인 방법 중 하나로 사용되고 있습니다. 이 알고리즘의 시간복잡도는 O(log(min(a, b)))으로 매우 효율적입니다.

특히 큰 수의 최대공약수를 구할 때 유리하며, 많은 수학적 알고리즘(예: 정수론, 암호학)에서도 자주 사용된다고 합니다.

 

<NEXT>

오늘은 유클리드 호제법 알고리즘을 통해 최대공약수와 최소공배수를 구하는 방법을 알아보았습니다. 다음에는 소수 판별에 사용되는 "에라토스테네스의 체"에 대해 알아보도록 하겠습니다. 감사합니다.