유클리드 알고리즘
-
01. 최초의 알고리즘알고리즘 2014. 11. 11. 13:09
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..