유클리드의 알고리즘 ( 최대 공약수 찾기 )

최대공약수 (GCD : 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 이며 이 중에서 제일 큰것은 10이며 이것이 바로 최대공약수이다.

수학 교과서 에서 최대 공약수를 구할 떄에는 소인수 분해를 이용하여 구한다. 다음과 같이 280과 30을 소인수 분해하면 최대 공약수와 최소 공배수를 구할 수 있다.
공통으로 나누어 떨어지는 수가 1 외에 없을 때 까지 소인수 분해한뒤 좌변의 수들을 모두 곱하면 최대공약수가 된다. 하지만 이 알고리즘은 앞의 두 정수의 곱셈의 예에서도 보았듯이 손으로 풀기에는 정말 좋은 알고리즘이지만 컴퓨터로 구현하기에는 좀 껄끄럽다. 왜냐하면 공통되는 인수를 구하는 작업과 그것을 나누는 작업이 컴퓨터에게는 여간 힘든 작업이 아니기 떄문이다.

유클리드의 알고리즘

유클리드의 알고리즘은 최대공약수의 성질을 이용하여 뺄셈과 두 값의 교환이라는 기본적인 동작으로만 최대공약수를 구할 수 있다. 우선 최대 공약수의 성질을 알아야겟다

A 와 B라는 정수가 있다고 하자 이 A와 B는 최대 공약수로서  G를 갖는다고 한다면 A와 B는 다음과 같이 표현할 수 있다.

A = a*G   (280 = 28 *10)
B = b *G (30 = 3*10)

소문자로 쓴 a 와 b는 각 A와 B에서 G 외의 인수들을 모두 곱한 값을 의미하고 a와 b는 서로소(공통되는 약수가 1밖에 없는 경우)이다.  그렇다면 A-B와 B 의 최대 공약수는 얼마 일까?

A-B = a*G - b*G = (a-b)*G

(a-b) 와 b는 역시 서로소 이므로 A - B 와 B의 최대 공약수는 역시 G 이다. 즉 쉽게 표현하면
GCD(u,v)라는  함수가 있어 이것이 u와 v의 최대공약수를 구하는 기능을 한다고할 때   이러한 성질을 가진다.

GCD(u,v) =GCD(u-v,v)    --------식1

최대공약수는 정수의 순서에 관계없으므로

GCD(u,v) =GCD(v,u)    --------식2

만약 0이 아닌 u라는 수와 0의 최대공약수는 얼마일까? 0은 어떤 수와 곱해도 0이기 떄문에 0의 약수는 정의상 모든 정수가 된다.( 0=u*0). 그러므로.....

GCD(u,0)  =u            ----------식3


자 그렇다면 280과 30의 최대공약수를 구해보자

GCD(280,30)   = GCD(250,30)    <- 식1 사용

= 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)    <-- 식 2를 사용
= GCD(20,10)
= GCD(10,10)
= GCD(0,10)
= GCD(10,0)
= 10   <-- 식 3을 사용

우리한테는 매우 긴 과정이다. 하지만 컴퓨터는 이런 것을 더 좋아한다. 왜냐하면 사용된 동작이라고는 정수의 뺄셈, 정수의 교환, 그리고 정수가 0인지 확인하는 것 밖에 없기 때문이다. 이런 간단한 동작은 그것이 아무리 길더라도 컴퓨터는 순간에 끝내버린다.

- 유클리드의 알고리즘을 말로 정의를 하자면

1. 임의의 두 정수 u와 v를 입력 받는다.
2.v가 u보다 크다면 v와 u의 값을 교환한다.
3.u에다 u-v의 값을 저장한다.
4. u가 0인가? 0이 아니면 2로 돌아간다. 
                  0이면 v가 최대공약수이다.

첨부파일 유클리드1 은  위 알고리즘을 이용한 간단한 소스파일이다.


모든 알고리즘은 개선될 여지가 있다. 그래서 알고리즘의 공부가 재미잇다 ㅋㅋ ㅠ.ㅠ
위에서 빼기를 이용한 유클리드 알고리즘은 입력되는 두 수 u와 v의 차이가 클때 실행 시간이 오래 걸린다.
예를 들어서 250과 30의 경우에는 뺄셈을 하여 10과 30으로 만드는데 무려 9번이나 뺄셈을 한다. 만약 32767 와 1의 최대 공약수를 구하는 경우는 무려.....32767번이나 뺄셈을 하게 된다. 이것이 문제이다.


그런대 250과 30을 뺄셈을 하여 만들 결과 10과 30을 자세히 살펴보면 10은 250을 30으로 나눈뒤의 나머지임을 알 수 있다. 즉 , 10 == 250 %30 인것이다. 이런 식으로 나머지 연산 (modulus operator: %)을 이용하면 9번의 뺄셈 대신에 한번의 % 연산으로 대체할 수 있다. 그래서  아래와 같은 식이 성립한다.


GCD(u,v) = GCD(u %v,v )     ------식 4

이 식 4를 이용하여 280과 30의 최대공약수를 구해보자.

GCD(280, 30)     =  GCD(10,30)   --------   식 4 (280 % 30 ==10)

=  GCD(30 , 10 )  -------  식 2
=  GCD(0 , 10 )    -------  식 4
=  GCD(10 ,  0 )  -------  식 2
 10                    -------- 식 3

위 와같이 하면 정말 같단해 진다.
a % b == c 일때 c는 항상 b보다 작은 성질이 있다. 즉 나머지는 젯수보다 작다는 것인데 이를 이용하면 뺄셈을 이용할 경우 항상 u와 v의 대소 비교를 했던 것과는 반대로 % 연산을 하면   대소가 분명해져서 % 연산후 무조건 두 값을 교환하면 되므로 if ( u< v ) .... 와 같은 문장을 없앨수 있다.

나머지 연산을 이용하여 최대공약수를 구하는 방법

1. 임의의 두 정수 u와 v를 입력받는다.
2. v가 0인가? 0이면 u가 최대공약수이다. 끝.
    0이 아니면 2.1  u에 u%v를 대입한다.
                   2.2 u와 v의 값을 교환한다.