유클리드 알고리즘(Euclidean Algorithm)

유클리드 알고리즘(Euclidean Algorithm)

유클리드 호제법 혹은 유클리드 알고리즘(Euclidean algorithm)은 두 수의 최대공약수를 구하는 방법이다.

유클리드 알고리즘의 핵심점인 부분은 다음과 같다.

'두 수 p,q(p > q)의 공약수의 집합은 p - q와 q의 공약수 집합과 같다'는 점을 이용한다.

간단한 증명을 통해 생각해보자.

Proof)

p, q의 공약수 g가 있다고 가정하자.

그러면 p = p'g, q = q'g로 쓸 수 있고, p - q = (p'-q')g이므로 g는 p - q와 q의 공약수가 된다.

따라서 p, q의 최대공약수 gcd(p,q)는 항상 p - q와 q의 최대 공약수 gcd(p - q, q)와 같게 된다.

이 성질을 이용하여 우리는 쉽게 어떤 수 p, q의 최대공약수를 구할 수 있다.

 

예를 들어 생각해보자.

12와 8의 최대 공약수를 구해보자.

gcd(12, 8) = gcd(8, 4) = gcd(4, 4) = gcd(0, 4)

결국 어느 한 수가 0이 되게 되는데 이때 0과 4의 최대 공약수는 4이므로 우리는 12와 8의 최대 공약수가 4임을 알 수 있다.

#include <iostream>
#include <cstdio>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
using namespace std;
 
int gcd(int p, int q)
{
    if (p < q)
        swap(p, q);
    if (q == 0)
        return p;
    return gcd(p - q, q);
}
 
int main()
{
    int p, q;
    scanf("%d %d", &p, &q);
 
    printf("%d\n", gcd(p, q));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 내용을 그대로 옮기면 다음과 같이 코드를 만들어 낼 수 있다.

하지만 p가 10억이고 q가 1이라면.. 상당한 시간과 메모리를 요구하게 될 것이다.

이를 해결하기 위해 좀 더 최적화를 시킬 필요가 있다.

아래 코드를 보고난 후 이야기 해보자.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int gcd(int p, int q)
{
    if (q == 0)
        return p;
    return gcd(q, p % q);
}
 
int main()
{
    int p, q;
    scanf("%d %d", &p, &q);
 
    printf("%d\n", gcd(p, q));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 코드는 p와 q의 대소 비교도 사라지고, '-' 연산이 아닌 '%' 연산으로 문제를 해결하고 있다.

이때 p < q일때의 입력이 들어올 경우 p % q = p이므로 비교 연산자는 자동으로 필요없어지게 된다.

(gcd(q, p)로 자동적으로 전환이 되는 것과 같아진다.)

이로인해 아래 링크처럼 한줄 코딩이 가능해질 수 있는 것이다.

http://www.crocus.co.kr/578