Euclid's Algorithm의 개선

모든 알고리즘은 개선될 여지가 있다. 그래서 알고리즘의 공부가 재미있다.

 

이전의 빼기를 이용한 유클리드 알고리즘은 입력되는 두 수 u 와 v의 차이가 클 때 실행시간이 오래 걸린다.

 

만약에 32767과 1의 최대공약수를 구하는 경우는 32767번이나 뺄셈을 하게 된다.

 

 그런데 250과 30을 뺄셈하여 만든 결과 10과 30을 자세히 살펴보면 10은 250을 30으로 나눈 뒤에 나머지임을 알 수 있다.

 

즉 10 = 250 % 30 인 것이다. 그래서 다음과 같은 식 4가 성립한다.

 

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

 

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

 

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

                      GCD(30, 10)

                      GCD(0, 10)

                      GCD(10, 0)

                   = 10

 

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의 값을 교환한다.