목록최대공약수 (1)

태코놀로지

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

최대공약수는 유클리드 호제법으로 구하는 것이 빠르다. 백준 온라인 저지 문제 중에서 간단하면서도 골치아프게 한 녀석이 있어서 기억하고자 글로 남긴다. 문제는 참 간단한 최대공약수 구하기. 그런데 시간 제한이 있기 때문에 난감했다. 정답은 나오지만 늘 '시간초과'로 인해서 정답처리가 되지 않았다. 익숙하고 무난한 문제였기에 설렁설렁 생각했는데 오산이었다. 시간을 줄이기 위해서 갖은 술수를 부렸으나 알고리즘 자체가 잘못되었고, 아마 이 문제는 딱 정해진 알고리즘으로만 풀이가 가능했으리라 생각한다. 제목에서도 언급한 것처럼 유클리드 호제법이라는 방법을 통해서 구현하여 단번에 통과되었다. 이전에 작성한 알고리즘도 틀린 것은 아니었지만, 확연히 연산 수에서부터 큰 차이가 난다. Source Code (Github..
Algorithm 2017. 1. 26. 22:52
Prev 1 Next