유클리드 호제법 (Euclidean-algorithm)

0. 글을 시작하며

---

우리가 문제해결을 하다보면 최대 공약수를 구해야하는 경우가 있습니다. 우선 가장 쉽게 생각해볼 수 있는 것은 초등학교 때 배우는 두 수를 모두 소인수 분해 후 공약수를 찾아 모두 곱하는 방식입니다. 예를 들어 우리가 27과 45의 최대공약수를 구한다고 할 때 보통 이런 그림을 그려서 최대 공약수를 구하곤 합니다.

그래서 우리가 두 자연수의 최대 공약수를 구해야하는 문제를 코드로 작성해서 해결해야할 때 가장 먼저 쉽게 떠올리고 접근하게 되는 방식이 바로 위의 방식일 것 입니다. 이를 코드로 다음과 같이 옮겨서 문제해결을 할 수 있지만 이 방식에는 한 가지 문제점이 있습니다 (여기서는 numberA가 numberB보다 크거나 같은 수임을 전제로 합니다).

private static int getGCD(int numberA, int numberB) {
    int gcd = 0;

    for(int i=numberB ; i>=1 ; i--) {
        if(numberA%i == 0 && numberB%i == 0) {
            gcd = i;
            break;
        }
    }

    return gcd;
}

여기서는 작은 수 numberB부터 시작하여 1까지 역으로 내려가면서 두 수의 최대 공약수를 찾고 있습니다. 각각 하나씩 확인해봐야하기 때문에 두 자연수의 크기가 작을 때에는 문제가 되지 않지만 두 자연수의 크기가 커지면 반복해야하는 수의 크기도 같이 커지기게 되고, 만약 두 수가 서로소인 경우 1까지 반복문이 계속 돌게되기 때문에 최악의 경우 O(N)의 시간복잡도가 발생하게 됩니다.

 

하지만, 오늘 이 글에서 다룰 "유클리드 알고리즘(Euclidean-algorithm)"을 활용하면 이 문제를 효과적으로 해결할 수 있습니다. 이번 글에서는 유클리드 알고리즘을 활용한 최대 공약수를 구하는 문제해결 방법과 그 구현에 대해서 알아보고자 합니다.

 

 

1. 정의

---

두 자연수의 최대 공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘 중 하나

유클리드 호제법은 기원전 300년 경 수학자 유클리드(Euclid)에 의해 발견된 두 자연수의 최대 공약수를 구하는 알고리즘 입니다. 유클리드 알고리즘이라고 표현하기도 합니다. 명시적으로 기술된 알고리즘 중 가장 오래된 알고리즘으로 알려져 있습니다.

 

 

 

2. 동작방식

---

이 알고리즘이 어떻게 동작하는 지 이해하기에 앞서서 우선 "호제법"이 무엇인지 확인하고 넘어갈 필요가 있습니다.

호제법

두 수가 서로 상대방 수를 나눠서 원하는 수를 얻는 전략

호제법은 "두 수가 서로 상대방 수를 나눠서 원하는 수를 얻는 전략"으로 유클리드 알고리즘이 이 방식으로 동작하게 됩니다. 호제법의 정의만 봐서는 무슨의미인지 잘 이해가 되지 않지만 이 정의를 읽고 유클리드 알고리즘의 동작을 설명하는 핵심 문장을 읽으면 이해가 더 쉬워집니다. 유클리드 알고리즘을 기억할 때에는 이 문장만 기억하시면 됩니다.

 

두 자연수 A와 B가 있고 A%B를 R이라 한다면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

그렇다면 이 문장을 식으로 옮겨보겠습니다. 여기서 GCD(A, B)는 A와 B의 "최대 공약수"를 의미 합니다.

 

GCD(A, B) = GCD(B, A%B)

 

끝 입니다. 이 논리를 프로그래밍 언어로 그대로 작성하여 우리는 두 자연수의 최대공약수를 구해야하는 문제를 효과적으로 해결할 수 있습니다.

 

 

3. 구현

---

유클리드 알고리즘을 구현하는 방식은 크게 두 가지 "재귀" or "반복" 입니다. 구현이 복잡하고 어려운 알고리즘이 아니기 때문에 이해하시기에 어려움이 없을 것으로 생각됩니다. 그래서 따로 구체적인 설명없이 구현 내용만 제시하도록 하겠습니다.

 

해당 구현에서는 numberA가 numberB보다 크거나 같은 수임을 전제로 하고 있습니다.

// 재귀를 활용한 구현
private static int getGCD(int numberA, int numberB) {
    if(numberB == 0) {
        return numberA;
    }
    return getGCD(numberB, numberA%numberB);
}

// 반복문을 활용한 구현
private static int getGCD(int numberA, int numberB) {
    int divider;
    while(numberB > 0) {
        divider = numberA%numberB;
        numberA = numberB;
        numberB = divider;
    }
    return numberA;
}

직관적으로 확인할 수 있듯이 재귀로 구현하는 것이 가장 간결하게 코드를 작성할 수 있습니다.

 

 

4. 최소 공배수(LCM, Least Common Multiple) 구하기

---

이제 여기서 한 걸음 더 나아가면 유클리트 호제법을 활용하여 "최소공배수 (LCM)"를 효율적으로 구할 수 있습니다. 처음에 생각해봤던 소인수 분해를 이용하는 방식으로 우리가 27과 45의 최소공배수를 구한다고 가정해보면 아래와 같이 접근하게 될 것입니다.

우리는 여기서 한 가지 사실을 발견할 수 있는 데 그것은 최대공약수와 최소공배수가 어떤 관계를 가지고 있다는 점입니다. 즉, 최소공배수는 두 수 사이에서 가장 작은 공배수를 구하는 개념이기 때문에 두 수를 곱한 값을 최대공약수로 나누는 것으로 이를 구할 수 있습니다. 따라서 우리는 유클리드 호제법으로 구한 최대공약수를 활용해서 최소공배수도 효과적으로 구할 수 있습니다.

 

즉, 다음과 같이 코드로 구현해볼 수 있습니다. 구현이 어렵지 않기 때문에 코드에 대한 자세한 설명은 생략하도록 하겠습니다.

// 재귀를 활용한 구현
private static int getGCD(int numberA, int numberB) {
    if(numberB == 0) {
        return numberA;
    }
    return getGCD(numberB, numberA%numberB);
}

private static int getLCM(int numberA, int numberB, int gcd) {
    return numberA * numberB / gcd;
}

 

 

5. 마치며

---

이렇게 유클리드 알고리즘으로 두 자연수의 최대 공약수를 구하는 문제를 효과적으로 해결 해보았습니다. 물론 유클리드 알고리즘을 수학적으로 접근한다면 훨신 깊은 내용들을 많이 다뤄야겠지만 (수학적 증명, 이론 등등...), 이 글에서는 유클리드 알고리즘을 이해하고 이를 프로그래밍언어로 구현하여 문제해결에 응용할 수 있도록 하는 것이 목적이기 때문에 수학적인 내용은 다루지 않는다는 점 양해 부탁드립니다.

 

감사합니다.

 

 

참고자료

---

유클리드 호제법 - 위키백과, 우리 모두의 백과사전