[프로그래머스][level 1] 최대공약수와 최소공배수 구하기

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12940

필요 지식

• 유클리드 호제법

해결 방법

최대공약수를 구하는 방법은 유클리드 호제법을 사용하지 않고, for문을 돌려 1부터 n 혹은 m까지 공통적으로 나눠지는 수를 찾는 방법이 있다. 하지만, 이 경우, n이나 m중에 작은 수만큼 비례하여 시간이 필요하게 된다. 즉 O(N)이다.

이것보다 좋은 알고리즘은 유클리드가 이미 오래전에 만들어 놓은 유클리드 호제법 알고리즘이다. 

유클리드 호제법의 아이디어는, A가 B보다 클 때, A = B*m +n일때, 공약수(A,B) = 공약수(B,n)를 증명하며 시작되었다. 이를 재귀로 생각한다면, 두 수 간에 최대로 큰 공약수를 찾을 수 있게 되는 것이다.

코드