두 수 a, b가 주어졌다고 할 때, 이 정수들을 나누어 떨어지게 하는 가장 큰 정수는 무엇일까요? 네, 바로 최대공약수입니다. 개념 자체야 너무나도 쉽게 와닿았는데, 이것을 코딩한다는 것은 굉장히 신선했습니다.

일단 간단하게 두 수의 최대공약수를 구하는 것부터 시작해 보겠습니다. 가장 먼저 생각할 수 있는 것은, 두 수 중 작은 것보다 작거나 같은 모든 수로 두 수를 나누어 보는 방법입니다. 딱 생각해 봤을 때도 굉장히 비효율적이겠죠? (부끄럽지만 제가 생각한 방법입니다..ㅠ)

def findGCD(a, b):
    small = min(a, b)
    for i in range(small, 0, -1):
        if a % i == 0 and b % i == 0:
            return i

>>> print findGCD(3, 5)
1
>>> print findGCD(6, 10)
2
>>> from time import time
>>> t0 = time()
>>> print findGCD(1500000, 2450000)
50000
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.36e-01

그래도 생각보다 오래걸리진 않네요~? ㅎㅎ 이 문제를 해결할 방법을 찾아보다가, 유클리드 호제법이라는 것이 있다는 사실을 기억해냈습니다. 사실 중학교때 즈음에는 그래도 종종 써먹던 방법이었던 것 같은데, 어느새 기억 저편으로 사라졌던 방법이네요. 어른이 다 되고 나서 다시 보니 정말 엄청난 알고리즘이더라구요 ^^ 참고 : 유클리드 호제법

자, 이제 유클리드 호제법을 이용해서 최대공약수를 찾아보면,

def Euclid_findGCD(a, b):
    large = a if a > b else b
    small = a if a <= b else b
    while large % small != 0:
        large, small = small, large % small
    return small

>>> print Euclid_findGCD(3, 5)
1
>>> print Euclid_findGCD(6, 10)
2
>>> t0 = time()
>>> print Euclid_findGCD(1500000, 2450000)
50000
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.09e-04

와우.. 마찬가지로 엄청나게 시간이 단축됨을 확인할 수 있네요. 정말 코딩보다도 알고리즘을 생각하는 것이 얼마나 중요한지 알 수 있게 해주는 예제였습니다.