01. 최초의 알고리즘

01. 최초의 알고리즘

  가장 오래된 알고리즘은 기원전 300년경에 만들어진 유클리드의 최대공약수를 찾는 알고리즘이다. 최대공약수는 2개 이상의 자연수의 공약수들 중에서 가장 큰 수이다.

  * 핵심

  유클리드는 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용하여 최대공약수를 찾았다. 예를 들면, 24와 14의 최대공약수는 24-14=10과 작은 수 14와의 최대공약수와 동일하다. 유클리드는 이 과정을 반복하여 최대공약수를 다음과 같이 계산하였다. 단, 최대공약수 (a,0)=a 이다.

  최대공약수(24, 14)

 = 최대공약수(24-10, 14) = 최대공약수(10,14)

 = 최대공약수(14-10, 10) = 최대공약수(4, 10)

 = 최대공약수(10-4, 4) = 최대공약수(6, 4)

 = 최대공약수(6-4, 4) = 최대공약수(2, 4)

 = 최대공약수(4-2, 2) = 최대공약수(2, 2)

 = 최대공약수(2-2, 2) = 최대공약수(0, 2)

 = 최대공약수 : 2

  유크리드의 최대공약수 알고리즘에서 뺄셈 대신에 나눗셈을 이용하면 매우 빠르다.

Euclid(a, b)

입력 : 정수 a, b; 단, a>=b>=0
출력 : 최대공약수(a, b)
if(b=0) return a
return Euclid(b, a mod b)

  최대공약수 (24, 14)에 대하여 Euclid 알고리즘이 수행되는 과정을 보자. 처음에 Euclid(24, 14)가 호출된다.

 = 최대공약수(24, 14) 

 = 최대공약수(14, 24 mod 14) = 최대공약수(14, 10)

 = 최대공약수(10, 14 mod 10) = 최대공약수(10, 4)

 = 최대공약수(4, 10 mod 4) = 최대공약수(4, 2)

 = 최대공약수(2, 4 mod 2) = 최대공약수(2, 0)

 = 최대공약수 : 2