유클리드 호제법과 최대공약수

최대공약수는 유클리드 호제법으로 구하는 것이 빠르다.

백준 온라인 저지 문제 중에서 간단하면서도 골치아프게 한 녀석이 있어서 기억하고자 글로 남긴다. 문제는 참 간단한 최대공약수 구하기. 그런데 시간 제한이 있기 때문에 난감했다. 정답은 나오지만 늘 '시간초과'로 인해서 정답처리가 되지 않았다. 익숙하고 무난한 문제였기에 설렁설렁 생각했는데 오산이었다.

시간을 줄이기 위해서 갖은 술수를 부렸으나 알고리즘 자체가 잘못되었고, 아마 이 문제는 딱 정해진 알고리즘으로만 풀이가 가능했으리라 생각한다. 제목에서도 언급한 것처럼 유클리드 호제법이라는 방법을 통해서 구현하여 단번에 통과되었다. 이전에 작성한 알고리즘도 틀린 것은 아니었지만, 확연히 연산 수에서부터 큰 차이가 난다.

Source Code (Github) def gcd(a, b): """ 최대공약수 구하는 함수 유클리드 호제법을 활용 dependency: prime_factorization input: integer return: integer """ bigger, smaller = 0, 0 if a > b: bigger = a smaller = b else: bigger = b smaller = a while bigger % smaller != 0: temp = bigger % smaller bigger = smaller smaller = temp return smaller