유클리드 최대공약수 알고리즘에 대해서 알아보자!
갑자기 든 생각인데, 길가는 사람 붙잡고 "280과 30의 최대공약수를 1분내로 구해보세요." 라고하면 몇명이나 구할 수 있을까?ㅋㅋ
여튼, 갑자기 물어보면 얼탈거같은 최대공약수를 구하는 알고리즘에 대해서 알아보자.
먼저 최대공약수(Greatest Common Divisor)란 주어지는 2개의 정수의 약수중에서 가장 큰 공통되는 약수를 말한다.
예를들어 280과 30의 최대공약수를 구한다고 해보자!
280의 약수: 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280
30의 약수: 1, 2, 3, 5, 6, 10, 15, 30
280과 30의 약수 중에서 공통되는것들은 1, 2, 5, 10 이렇게 4개이고 이중에서 가장큰 10이 바로 최대공약수(GCD)다.
초등학교 수학 교과서에서는 최대공약수를 구할때 소인수분해를 통해서 구하는걸 배웠는데, 280과 30을 소인수분해를 통해서 최대 공약수를 구하면 아래와 같다.
2 | 280 30
5 | 140 15
--------
28 3 <--- 28과 3을 동시에 나누어 떨어지는 숫자가 없음!위와 같이 공통으로 나누어 떨어지는수가 1외에 없을때까지 소인수분해를 한 다음, 좌변의 수를 모두 곱하면 최대공약수가 되고 이 경우에는 10이다.
하.지.만 사람이 손으로 계산을 하기에는 좋은 알고리즘 이지만, 컴퓨터에게 이렇게 계산을 하라고 시키기에는 조금 껄끄럽다.
왜냐하면 두개의 정수에게 공통되는 인수를 구하는 작업과, 이걸 나누는 작업이 컴퓨터한테는 쉽지않은 작업이기 때문이다.
유클리드 알고리즘
유클리드 알고리즘은 최대공약수의 성질을 이용해서 뺄셈과 두 값의 교환이라는 기본적인 동작만으로 최대공약수를 구할 수 있다.
그러면 최대공약수의 성질이 뭐냐?
A와 B라는 정수가 있다고 가정할때, 이 A와 B는 최대공약수로 G를 갖는다고 가정하면 A와 B는 아래처럼 표현할 수 있다.
- A = a x G (280 = 28 * 10)
- B = b x G (30 = 3 * 10)
위에서 소문자로 작성한 a,b는 각각 A,B에서 최대공약수G를 제외한 나머지 인수들을 모두 곱한 값을 의미한다. (위에 280을 2와5로 나누고 28이 남은것 처럼)
그리고 a,b는 서로소이다. (서로소는 공통되는 약수가 1밖에 없는 경우를 의미한다.)
그렇다면 A-B와 B의 최대 공약수는 얼마일까??
A-B = a x G - b x G = G(a-b)
(a-b)와 b역시 서로소 이므로 A-B와 B의 최대공약수 역시 G로 동일하다.
280과 30의 최대공약수가 위에서 구한것처럼 10이고, 250과 30의 최대공약수 또한 10인걸 확인할 수 있다.
즉! GCD(u, v)라는 함수가 u, v의 최대공약수를 구하는 함수라고 가정할때, GCD(u, v) == GCD(u-v, v)와 동일한 값이라는걸 알 수 있다.
동시에 최대공약수의 정수는 순서에 상관이 없기 때문에, GCD(u, v) == GCD(v, u) 이 식도 성립한다.
(30과 280의 최대공약수와 280과 30의 최대공약수는 동일하니까~)
만약 0이아닌 숫자와 0의 최대공약수는 얼마일까???
0은 어떤숫자와 곱해도 0이기 때문에, 0의 약수는 정의상 모든 정수가 된다.
따라서 GCD(u, 0) == u다.
그러면 위 3가지의 특징을 이용하면 아래와같이 정리할 수 있다.
- 임의의 두 정수 u, v를 입력받는다.
- v가 u보다 크다면, v와 u의 값을 교환한다.
- u에다 u-v 값을 저장한다.
- u가 0이라면 v가 최대공약수이고, 아니라면 반복한다.
그러면 280과 30의 최대공약수를 위의 방식대로 계산하면 아래와 같다.
= GCD(280, 30)
= GCD(250, 30)
= GCD(220, 30)
= GCD(190, 30)
= GCD(160, 30)
= GCD(130, 30)
= GCD(100, 30)
= GCD(70, 30)
= GCD(40, 30)
= GCD(10, 30) ==> 두개 인수의 값을 서로 교환
= GCD(30, 10)
= GCD(20, 10)
= GCD(10, 10)
= GCD(0, 10) ==> 두개의 인수의 값을 서로 교환
= GCD(10, 0) ==> 두번째 인수의 값이 0 이므로, 첫번째 인수의 값 10이 최대공약수가 됨.
손으로 직접 하면 매우 긴 과정이지만, 컴퓨터는 이런 단순한 정수의 덧셈과 교환, 그리고 0인지 아닌지만 판단하면되는 아주 간단한 로직을 더 좋아한다.
개선을 할수는 없을까?
위의 알고리즘은 입력되는 두개의 숫자 u, v의 차이가 크면 클수록 실행시간이 오래걸린다.
예를 들어서 32767과 1의 최대공약수를 구하는 경우라면, 32767번이나 뺄셈 연산을 해야한다 😱
그런데 250과 30을 뺄셈해서 만든 결과 10과 30을 자세히 살펴보면, 10이란 숫자는 250 % 30 연산의 값이라는걸 알 수 있다!
즉 10 == 250 % 30이고, 이런식으로 나머지 연산을 이용하면 더 빠르게 값을 찾아낼 수 있다.
GCD(u, v) == GCD(u%v, v)
이 식을 이용해서 280과 30의 최대공약수를 다시 구해보자.
= GCD(280, 30)
= GCD(10, 30)
= GCD(30, 10)
= GCD(0, 10)
= GCD(10, 0)
위와같이 계산 과정이 더 단순해진다.
#include <stdio.h>
int get_gcd(int u, int v) {
if(u < 0 || v < 0) {
return 0;
}
int t;
while (v) {
t = u % v;
u = v;
v = t;
}
return u;
}
int main(int argc, const char * argv[]) {
printf("280 and 30's GCD is %d\n", get_gcd(280, 30));
printf("170 and 15's GCD is %d\n", get_gcd(170, 15));
return 0;
}