유클리드 호제법

유클리드 호제법을 이용한 최소공배수 구하기 (C언어)

문제 : BOJ_5347번 LCM

백준 알고리즘 기본 문제를 풀다 보면, 최대 공약수와 최소 공배수를 구하는 문제들을 마주하게 됩니다. 위에 가져온 문제를 보면 두 수 a와 b를 입력해서 최소 공배수를 출력하는 문제인데, 시간 복잡도를 고려하지 않는다면 이중 for문을 이용한 이런 무식한 코딩도 가능합니다.

#include<stdio.h>
int main(void) {
    int num;
    scanf("%d",&num);
    for(int a=1;num>=a;a++){
        long long num1, num2;
        long long mul1, mul2;
        scanf("%lld %lld",&num1,&num2);
        for(mul1=1;num2>=mul1;mul1++){
            for(mul2=1;num1>=mul2;mul2++){
                if(mul2*num2==mul1*num1) break;
            }
            if(mul2*num2==mul1*num1) break;
        }
        printf("%lld\n",mul2*num2);
    }
    return 0;
}

(시간초과에 걸리는 무식한 코딩)

언급했듯이 다소 무식한 방법이지만, 두 수를 num1, num2라고 할 때 for문 안에 a*num1 = b*num2 가 될 때까지 a와 b를 이중 for문 안에서 탐색하는 방법입니다. 위 소스를 컴파일하면 원하는 최대 공배수를 구할 수 있지만 num1과 num2는 백만까지 커질 수 있으므로 이런 코딩은 시간 제한 1초를 넘어버리는 for문을 초래하고 맙니다.

이러한 시간복잡도를 극복하기 위해 알고리즘에서 최대 공약수를 빠르게 구하는 방법이 바로 유클리드 호제법인데요. 일단 정의부터 확인하자면,

유클리드 호제법

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.

정수 a, b, q r (b ≠ 0)에 대하여 a = bq + r,이면 G(a, b) = G(b, r)가 성립한다.

〈증명〉

G(a, b) = g라고 하자. 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다.

a = bq + r로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다.

G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다.

귀류법을 적용하여 결론을 부정해보자.

어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn= dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, r) = g가 성립한다.

출처:[네이버 지식백과] 유클리드 호제법 (통합논술 개념어 사전, 2007. 12. 15., 청서출판)

쉽게 말해 a와 b의 최대 공약수를 구하기 위해, 몫을 q 나머지를 r로 표현한다면,
a = bp + r
이고 위 식에서 a와 b의 최소 공배수는 b와 r의 최소 공배수와 같다는 정리입니다.

프로그래밍상 증명의 내용보단 사용법을 정확히 알아야되지만, 위의 증명을 짧게 해석해보자면,

a와 b의 서로소를 a'와 b'로 정하지고 최대공약수를 g라고 정했을 때,
나머지 r이 g(a′ - b′q)가 되는데, 여기서 b'와 a′ - b′q가 서로소임을 결론을 부정하여 귀류법으로 증명하는 과정입니다.
(b'와 a′ - b′q가 서로소가 아니라면 a'와 b'에 공약수가 생기면서 둘이 서로소라는 전제에 위배)

증명은 이쯤에서 하고, 프로그래밍을 목적으로 봤을 때 반복문을 이용해서 유클리드 호제법을 구현한다면,
a와 b의 최대 공약수는 b와 r의 최대 공약수와 같고, b와 r의 최대 공약수는 또 다른 b'과 r'의 최대공약수와 같기 때문에,
나머지인 r(n)'이 0이 되는 경우에서의 b가 최대 공약수임을 알 수 있습니다.

말로 표현하면 어렵지만, 위키백과에서 가져온 유클리드 호제법의 예를 보면,

유클리드 호제법을 이용한 최대공약수 구하기 (출처 : 위키백과)

마지막에서 72 = 36 x 2(몫) + 0(나머지) 임을 알 수 있습니다.
그러므로 a,b를 호출 시, b가 0이 되고, a가 마지막 최대 공약수가 되는 함수식을 만든다면, ```c int gcd(int a, int b) { int c; while (b) { c = a; a = b; b = c % a; } ```

(유클리드 호제법 함수)

위와 같은 함수로 나타낼 수 있습니다. (b==0 일 때 while 문이 종료됨으로)
*최대 공약수는 편의상 gcd(greatest common divisor)로 많이 씁니다.
위의 유클리드 호제법을 이용해서 앞서 소개해드린 백준 문제를 다시 풀어본다면,

유클리드 호제법을 응용한 풀이

#include <stdio.h>
int gcd(int a, int b);
int main() {
    int roof,i;
    scanf("%d", &roof);
    for (i = 1; i <= roof; i++) {
        int num1, num2, num3;
        scanf("%d %d", &num1, &num2);
        if (num1 >= num2) {
            num3 = gcd(num1, num2);
        }
        else num3 = gcd(num2, num1);
        printf("%d\n", num3*(num1 / num3)*(num2 / num3));
    }
    return 0;
}
int gcd(int a, int b) {
    int c;
    while (b) {
        c = a;
        a = b;
        b = c % a;
    }
    return a;
}

(5347번 풀이 코딩)


위와 같이 최대 공약수를 구한 뒤, num1과 num2를 최대 공약수로 나눈 몫을 최대 공약수에 곱해주는 방식으로 최소 공배수를 출력 할 수 있습니다.