최소 공배수 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

두 수의 최소 공배수 구하기

두 수의 최소 공배수를 구하는 방법을 알아보자.

배수를 구하는 방법은..  다들 알 것이라 굳게 믿는다.

자, 처음에 소개할 방법은 가장 기초적이고 직관적이다!

이중 반복문을 순회하면서 a * i == b * j 를 만족할 때 값을 반환한다.

최악의 경우는 두 수가 서로소인 경우이고, 이 때의 최소 공배수는a * b이다.

따라서 각각의 반복문의 범위는 b, a 까지로 한정된다.

물론 간단한 만큼 성능은 떨어진다.

최악의 경우에서의 시간 복잡도는 O( a*b )이므로 O( n^2 )에 근사하다고 볼 수 있고,

입력값이 각각 46341, 46340 인 경우에서 평균 소요시간은 4896 ms 였다.

위의 방식이 느린 이유는, 실패가 뻔한 곳까지 조사하기 때문인데,

이미 a*i < b*j 임에도 불구하고 계속해서 j값을 증가시키고 있음에 주목하자.

그렇다면 안쪽에 if(a*i < b*j) break; 를 넣으면 해결되지 않을까?

놉.  그래봤자 연산량은 절반으로밖에 줄지 않는다.

여전히 시간 복잡도는 O( n^2 ) 이다.

x, y축을 각각 a*i, b*j으로 하는 문제영역을 그려보자.

최소 공배수는 y=x에 있을것이며, 다른 곳은 볼것도 없다.

여기서 안쪽에 if(a*i < b*j) break; 를 넣으면 y<x만 제쳐질 뿐,

아직 아랫쪽 영역이 남아있다.

아래처럼 아랫쪽 영역까지 쳐내고 대각선 근처만 탐색해야,

효율적으로 정답을 찾을 수 있다. 

어렵게도 설명했다.

요점은 답이 있을듯한 부분만 찾아라 이다.

아래 코드는 위의 컨셉을 활용한 알고리즘이다.

a, b의 배수인 x, y가 서로 근접하게 증가하는 것이 핵심이다.

최악의 경우(서로소)에서의 시간복잡도는 O( a + b ) 이고,

입력값이 각각 46341, 46340 인 경우에서 평균 소요시간은 159 μs 였다.

충분히 만족할만한 성능을 이끌어냈지만,

수학을 활용한다면 더욱 개선시킬 수 있다.

최소 공배수(lcm)와 최대 공약수(gcd)의 관계를 이용하는 것이다!

lcm = a * b / gcd임을 이용하자!

a, b를 gcd로 약분하자.

이것을 a', b'라고 하면, 이 두 수는 서로소이므로 a', b'의 최소공배수는 a' * b' 이다.

따라서 a, b의 최소 공배수는 gcd * a' * b' 이다.

다음은 위의 결과를 이용한 구현이다.

마지막 행의 반환문을 주목하자.

a * b는 오버플로우가 발생할 수 있으므로, 중간 연산값을 최소화하기 위해 먼저 나눗셈을 수행했다.

이 알고리즘은 최대 공배수를 구하는 연산이 전체를 지배하므로 시간복잡도는 O( log( a + b ) ) 이고,

입력값이 각각 46341, 46340 인 경우에서 평균 소요시간은 74 ns 였다.

3개 이상일 때, 최소 공배수 구하기

lcm(a, b, c) = a * b * c / g / g 이고,

lcm(a, b, c, d) = a * b * c * d / g / g / g 이다.

증명

숫자가 여러개일 때, 최대 공약수와 최소 공배수의 관계를 참조하기 바란다.