본문 바로가기

# Foundation/기초수학

최소 공배수 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    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, bgcd로 약분하자.

이것을 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 이다.


증명

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


'# Foundation > 기초수학' 카테고리의 다른 글

피보나치 수열 알고리즘  (0) 2018.11.03
소수 알고리즘  (0) 2018.10.26
최대 공약수와 최소 공배수의 관계  (0) 2018.10.24
최대 공약수 알고리즘  (0) 2018.10.22
약수 알고리즘  (0) 2018.10.21