[Algorithm] 유클리드 호제법 (Euclidean Algorithm)

날짜:


유클리드 호제법 (Euclidean Algorithm) 이란? 


두 양의 정수나 다항식의 최대공약수를 구하기 위한 방법으로 유클리드 알고리즘이라고 부르기도 한다. 유클리드 호제법의 정의는 아래와 같다.

어떤 두 양의 정수 a, b에 대하여 (a > b) a = bq + r 이라면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.



증명

gcd(a, b) 가 a 와 b 의 최대공약수라고 하자. gcd(a, b) = G 일 때, 서로소인 어떤 두 정수 A, B 에 대하여 a = AG, b = BG 임을 알 수 있다. (A와 B가 서로소이기 때문에 공약수가 존재하지 않는다.) 따라서 a = bq + r 에 대입하면 GA = GBq + r 이므로 r = G(A - Bq) 이다. 이 식을 통해 r 과 G 가 공약수를 가지고 있다는 것을 알 수 있다. 이 때,  r = G(A - Bq), b = GB 를 봤을 때 B 와 A - Bq 가 공약수를 가지지 않은 서로소라고 한다면 r 과 b의 공약수는 G 가 된다. 즉 gcd(b, r) = G 이다.

gcd(B, A - Bq) 가 서로소가 아닌 공약수를 가지고 있다고 가정하고 이 때의 공약수를 m이라고 하자. 즉 gcd(B, A - Bq) = m이다. 그렇다면 다시 B = xm, A - Bq = ym 이 된다. 따라서 A = Bq + ym = xqm + ym = (xq + y)m 이 되는데 이는 A 가 m 이라는 공약수를 가지고 있으며, A 와 B 의 공약수가 m 이라는 것이므로 위에서 "서로소인 어떤 두 정수  A, B 에 대하여" 란 정의에 모순이 된다. 따라서 gcd(B, A - Bq) 는 공약수가 존재하지 않는 서로소가 된다. 

B 와 A - Bq 가 서로소이므로 gcd(b, r) = G 라는 것이 증명된다.



유클리드 호제법은 2가지 방법으로 구현할 수 있다.


1. 반복문을 이용한 방법

long long gcd(long long a, long long b){
	long long t;
	while(b != 0){
	    t = a % b;
	    a = b; b = t;
	}
	return a;
}


2. 재귀함수를 이용한 방법


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

구현 방법만 다를 뿐, 사실 b가 0이 될 때 까지 계속 a 와 b를 나눈 나머지를 구하고, 다시 b와 그 나머지의 공약수를 구하는 방법이다. 백준의 1934. 최소공배수 문제를 한 번 풀어보도록 하자.





[백준] 1934. 최소공배수


문제





풀이

문제를 보고 '유클리드 호제법은 최대공약수를 구하는 알고리즘이 아닌가? 문제는 최소공배수를 구하는 것인데 
유클리드 호제법이랑 무슨 상관이 있지?' 라고 생각할 수도 있다. 말 그대로 유클리드 알고리즘은 최대공약수를 구하는 방법이다. 
유클리드 호제법은 일단은 보류하고, 최소공배수란 무엇인가? 어떤 두 양의 정수의 배수들 중에서 공통적으로 가지고 있는 배수 중 가장 작은 배수를 최소공배수라고 한다. 그렇다면 최소공배수는 어떻게 구할까? 문제의 예시에서 나온 6과 15의 배수를 쭉 써보자.

6 -> 12 -> 18 -> 24 -> 30 -> 36 -> 42 -> 48 -> 54 -> 60 -> 66 -> 72 -> 78 -> 84 -> 90 -> ...
15 -> 30 -> 45 -> 60 -> 75 -> 90 -> ....

이 중 공통적인 배수 (공배수)는 아래와 같다. 

30 -> 60 -> 90 -> ...

따라서 6과 15의 최소공배수는 30이라는 결론이 나오며, 위와 같이 두 수의 배수를 쭉 찾으면서, 그 중 가장 먼저나오는 공배수를 구해도 된다. 이 방법을 코드로 옮기면 아래와 같이 구현할 수 있다. 큰 수의 배수 x를 vector에 담으면서, 작은 수를 x보다 작을 때까지 배수를 구해주면서, 이 작은 수의 배수가 vector 안에 있는지 체크해주고 없으면 큰 수의 다음 배수를 구해주는 과정을 반복해준다. 위의 6, 15 를 예를 들어보면 아래와 같다.

15 * 1 = 15 일 때 (15를 벡터에 삽입)
6 -> 12

15 * 2 = 30 일 때 (30을 벡터에 삽입)
12 -> 18 -> 24 -> 30 (30이 vector 안에 있으므로 종료)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

long long gcd(long long a, long long b){
	long long t;
	while(b != 0){
		t = a % b;
		a = b; b = t;
	}
	return a;
}

void check1(long long a, long long b){
    int x = max(a, b), y = min(a, b);
    vector<long long> div;

    int i = 1, j = 1;
    long long mul = y;
    while(true){
        div.push_back(x * j);
        while(mul * i <= x * j){
            for(int k = 0; k < div.size(); k++){
                if(div[k] == mul * i){
                    cout << div[k] << '\n'; return;
                }
            }
            i++;
        }
        j++;
    }
}


int main(int argc, char* argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
    int T; cin >> T;
    for(int i = 0; i < T; i++){
        int a, b; cin >> a >> b;
        check1(a, b);
    }
	
 
	return 0;
}


그렇다면 위 방법은 좋은 방법일까? 두 수가 모두 적은 수라면 이 방법으로도 해결할 수 있겠지만 두 수가 어마어마하게 큰 수라면 적은 시간 안에 해결하기 힘들 것이다. 그럼 이보다 더 적은 시간 안에 해결할 수 있는 방법은 무엇일까?
사실 최소공배수를 구하는 방법은 초등학교 교육 과정에 나온다. 우린 이미 그 방법을 알고 있다는 말이다! 가령 8262와 468의 최소공배수는 아래와 같이 구한다.
8262를 최대공약수로 나눈 수인 459와 468을 최대공약수로 나눈 수인 26을 곱하고, 마지막으로 최대공약수를 곱하면 두 수의 최소공배수가 나온다. A와 B의 최대공약수가 G일 때, 두 수의 최소공배수는 아래 식과 같으며, 이를 코드로 구현하면 아래의 코드와 같이 나온다.

(A / G) * (B / G) * G

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

long long gcd(long long x, long long y){
	long long t;
	long long a = max(x, y), b = min(x, y); 
	while(b != 0){
		t = a % b;
		a = b; b = t;
	}
	return a;
}



int main(int argc, char* argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int T; cin >> T;
    for(int i = 0; i < T; i++){
        int a, b; cin >> a >> b;
        cout << a * b / gcd(a, b) << '\n';
    }
	
 
	return 0;
}

그렇다면 처음의 방법과 두번째의 방법은 얼마나 시간 차이가 날까? 사실 두번째 코드는 시간을 측정할 필요도 없이 단순 계산이기 때문에 매우 짧은 시간이 걸린다. 시간이 걸리는 부분이라곤 최대공약수를 구하는 과정인데, 이마저도 두 수가 매우 큰 수가 아닌 이상 오랜 시간이 걸리지 않는다. 첫번째 코드의 시간이 문제인데, 이를 측정해보면 아래와 같이 나온다.


작은 두 수로 해봤자 큰 의미가 없을테고, 문제에서 허용하는 수의 범위 내에서 적당히 큰 두 수를 입력으로 넣어본 결과 첫번째 방법은 대략 3초 정도가 걸렸고, 두번째 방법은 1e-05라는 시간이 걸렸는데, 이를 환산해보면 0.00001초라는 매우 적은 시간이 나온다. 말했듯이 두번째 방법의 시간은 의미가 없고 첫번째 방법만 보자면 1초 안에 계산을 끝내야하는 문제의 조건과 달리 3초라는 시간이 걸렸기 때문에 시간 초과를 받았을 것이다.  

유클리드 호제법에 대해선 문제도 잘 나오지 않고 관련 학과가 아니면 거의 볼 일도 없을 것이다. 필자도 대학 2학년 때 암호학 강의를 들었을 때 이 알고리즘에 대해서 배운 적이 있었는데, 그 이후론 언제 썼는지 기억도 안난다. 그래도 그냥 상식으로 알아두고 넘어가면 어떨까 싶다.



출처 및 참고 



현대암호학 (제2판 - 이민섭 저자)



댓글

댓글 쓰기