본문 바로가기

# Foundation/기초수학

최대 공약수 알고리즘

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

두 수의 최대 공약수 구하기

이번에는 두 숫자의 최대 공약수를 구하는 방법에 대해서 알아보자.

약수를 빠르게 찾는 방법은 이전 게시글을 참고하도록 하자.


먼저 쉽게 가보자. 지금보다 큰 공약수가 나올때마다 갱신하면 된다. 

물론 성능은 보장할 수 없다.


a = 1,000,000,000 이고 b = 876,543,210 일 때, 평균 2711 ms가 걸렸다.

반복문이 min(a, b)번 만큼 순회하므로, 시간 복잡도는 O( min(a, b) ) 이고,

큰 입력값이나 횟수나 들어온다면 더더욱 성능을 보장할 수 없다.


여기서 잔머리를 한번 굴려보자, 뒤에서 첫 공약수가 최대 공약수임을 눈치챘다면

공약수가 상당히 뒤쪽에 있는 경우에는 비약적인 성능향상을 기대할 수 있다.


하지만 우리는 최대 공약수가 어느쪽에 있는지 모를 뿐 더러,

입력에 비해 최대 공약수가 현저히 작다면 개선하기 전과 다를게 없다.


a = 1,000,000,000 이고 b = 876,543,210 일 때, 최대 공약수는 10 이므로 최악의 케이스에 가깝다.

시간 복잡도도 개선하기 이전과 거의 다를것이 없으며, 수행시간은 평균 2923 ms가 걸렸다.


방법은 없는걸까?

있다. 다만 수학적으로 접근해야 한다.


a, b의 최대 공약수란 a%n==0 , b%n==0을 동시에 만족하는 n의 최대값이며,

a/n , b/n , (a%b)/n은 서로소가 된다는 성질을 이용하자.

a , b의 최대 공약수는 b , a%b의 최대 공약수와 같다.


이 매커니즘을 유클리드 호제법이라고 하고,

구체적인 증명은 아래와 같다.



아래는 유클리드 호제법으로 개선된 재귀 알고리즘이다.


ab의 배수일 때, a%b0이 될 수 있음에 주의하자.

두 변수의 진행과정은 피보나치 수열과 같으므로, 시간 복잡도는 O( log(a+b) ) 이다.


시간복잡도 증명과정은 다음과 같다.



자, 전체 연산량이 선형 증가에서 로그 증가로 바뀌었다!

a = 1,000,000,000 이고 b = 876,543,210일 때, 평균 소요시간도 167 ns으로 줄었다.

(밀리 세컨드가 아니다, 무려 나노 세컨드다!)


하지만 재귀함수는 호출스택을 관리하는 오버헤드가 있으므로,

반복문으로 구현하여 성능을 더욱 향상시킬 수 있다.


평균 소요시간도 90 ns 로 줄었다. 

다른 방법들도 자세하게 알고싶으면 다음 pdf 파일을 참고하자.


10-Gcd.pdf



3개 이상일 때, 최대 공약수 구하기 

간단하다. 예를들어 a, b, c가 있다고 가정했을 때,

a, b, c의 최대 공약수는 a, b의 최대 공약수의 약수임이 자명하다.


즉, gcd(a, b, c) == gcd( gcd(a, b) , c ) 이다.


아래는 위의 특성을 적용한 코드이다.




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

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