반응형


Problem Solving 의 정수론 분야 중 두 수의 최대공약수최소공배수를 이용한 문제들은 매우 자주 등장하는 편이다.
구하는 방법은 여러가지가 있는데...


방법 1) 소인수 분해 (Prime Factorization)
중학교 때 배우게 되는 소인수 분해를 이용한다
어떤 수의 모든 소인수를 구하는 방법은 소수구하기 알고리즘을 이용한다.

소인수분해는, a 와 b 를 소수로 나눌 수 있는 만큼 인수분해하여, 최대공약수는 두 수의 공통된 소인수들 중에서 차수가 최소인 값들의 곱이 되며, 최소공배수는 두 수의 모든 소인수들 중에서 차수가 최대인 값들의 곱이 된다.


이 방법은 수학시간에 배운 직관적인 방법이고, 많은 이들에게 익숙하지만 위에서 보듯이 코딩으로 옮기기에는 꽤나 귀찮다는 단점이 있다. 또한 두 수 a, b 의 모든 소인수를 구해서 저장해 놓아야 하므로 별도의 메모리를 필요로 한다. ( 위의 코드는 10000 까지의 소인수에 대해서 구현한 코드 )


방법 2) Brute force
최대공약수의 정의를 이용하여, brute force 방법으로 직접 구한다.
즉, 두 수 a, b 를 나누어서 나머지가 0 이 되는 수들 중에서 가장 큰 숫자를 구하면 이 숫자가 최대공약수가 되며, 두 수 a, b 의 배수를 구하여 공통된 배수 중 가장 작은 숫자를 구하면 이 숫자가 최소공배수가 된다.

위의 코드에서 만약 a, b 간의 공약수가 존재하지 않는 경우는 두 수의 최대공약수는 자연스럽게 1이 되며, a, b 간의 최소공배수 중 가장 클 가능성이 있는 수는 a*b 가 되므로 a*b 까지만 검사를 하면 된다.

이 방법은 최대 a*b 번의 연산을 해야 하므로,  a 와 b 가 커질수록 수행시간이 급격히 늘어난다.


방법 3)
Euclid's algorithm - Using Recursion
사실 최대공약수와 최소공배수를 구하는 것은 고대 그리스의 수학자, 유클리드가 고안한 "유클리드 알고리즘"(Euclid's algorithm) 을 쓰면 간결하게 해결할 수 있다. 이 방법은 The Art Of Computer Programming 의 제 1장에도 소개된 바 있다.
a, b 중 큰 수를 a, 작은 수를 b 라 하자. 이 두 수의 최대공약수를 구하려면 a 를 b 로 나눈다. 이 연산을 한 후에 b 와 a%b 를 갖고 어느 한쪽이 0 이 될때까지 이 과정을 계속 반복한다. a%b 가 0 이 될 때의 b 가 바로 최대공약수가 된다. 이를 코드로 옮기면 다음과 같다.


최대공약수와 최소공배수의 성질을 이용하면 아래와 같이
최소공배수 = (a*b) / 최대공약수
최대공약수 = (a*b) / 최소공배수
가 되므로, 최대공약수나 최소공배수 둘 중 하나만 구하면 나머지 하나는 쉽게 구할 수 있다.


방법 4) Euclid's algorithm - Using Iteration
방법 3 은 매우 간결한 코딩이 가능하지만, 재귀호출을 이용한다는 단점이 있다. 재귀호출은 상당히 비싼 작업이므로 이를 좀더 효율적인 iteration 버전으로 바꿀 수 있다. 실제로 방법 3은 a, b 가 매우 큰 서로소일 경우 답을 얻는데 꽤 오랜 시간이 걸리게 된다.



방법 5) Euclid's algorithm - Using Iteration, Original Version
유클리드가 처음 이 알고리즘을 제안했을때 사실은 modular 연산을 사용하지 않고, 아래와 같이 뺄셈 연산을 이용했다 한다.
 
방법5 는 방법 4와 비교하여, tmp 변수를 사용하지 않아도 되므로 메모리를 약간 절약한다는 장점이 잇다 ^^

유클리드 알고리즘의 증명 = 자세한 설명은 생략한다 Wikipedia 참고
유클리드 알고리즘의 시간복잡도 = O(n^2), n = length of integer bits, 그 이유는 n-bit 숫자 나눗셈 연산의 시간복잡도가 O(n(m+1)) 이기 때문이다 ( m 은 몫의 길이 )

3개 이상의 수에 대해 최소공배수와 최대공약수를 구할 때는, 두 수의 최소공배수와 최대공약수를 구한 후, 이 수와 나머지 수들에 대해 최소공배수와 최대공약수를 구하면 된다.

유클리드 알고리즘을 처음 보았을 때 무릎을 쳤던 기억이 난다. 그래서 최대공약수와 최소공배수에 대해서 글을 반드시 함 써보려 했는데... 위키피디아에 유클리드 알고리즘이 깔끔하고 멋지게 정리가 되어 있었다 ㅋ

+ Recent posts