유클리드의 최대공약수 알고리즘

#유클리드가 기원전 300년에 쓴 #'원론'은 20세기까지도 교과서로 활용될 정도로 그 깊이가 엄청나다.

당시 사람들은 유클리드라는 말이 #기하학 을 의미하는줄 착각할 정도였다고 하니
얼마나 이 책의 영향이 큰지는 짐작할 수 있을 것이다.

흔히 있는 서문이나 책에 대한 헌사 한 줄 없이 빽빽한 수학 공식으로 이루어진 이 책이야말로 알고리즘의 가장 근원적인 엑기스 정신을 담고 있다고 해도 과언이 아닐 것이다.


이 책에는 2000년도 더 된 #최대공약수 구하기 라는 알고리즘이 등장한다.
매우 유명하고 중학교 수학시간에 누구나 배우는 원리이기 때문에 친숙할 것이다.

이 알고리즘은 간단하다.

두 수 m과 n 이 있을 때(m>n)
m을 n으로 나눈 나머지 r이 0이면 n이 최대공약수가 되고
나머지가 0이 아닐 경우, m을 n으로, n을 r로 바꿔서 다시 과정을 반복하다보면
최종적으로 r=0일때의 n값이 최초 m의 최대공약수가 된다.

다소 설명이 복잡하니 간단한 예를 들어서 보자.

10과 3이 있다.

m=10
n=3

10%3은 1이다.
나머지가 0이 아니므로

m=3
n=1

3%1은 0이다.

따라서 두 수의 최대공약수는 1이 되는 것이다.


데이터 사이언티스트 백준은 이를 가르켜 군더더기 하나 없는 아름다운 시와 같은 알고리즘이라고 칭했다. 마치 이 알고리즘을 보고있자면 경쾌한 왈츠 음악이 들리는 것 같다고..

이를 간단한 c언어로 표현하면 아래와 같이 깔끔한 코드가 된다.

int gcd(int m, int n){       if (n>m) {             swap (m,n);       }             while (n>0){             r=m%n;             m=n;             n=r;       }       return m; }

이렇듯 2000년이 지나도 효율적인 알고리즘은 사라지지 않는다.
아무리 복잡한 일이더라도 진리에 가까울수록 단순해지는 법이다.

군더더기없는 탄탄한 근육 같은 알고리즘을 만드는 것,
그것이 진정한 데이터 사이언티스트의 자세일 것이다.