이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
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의 최대 공약수와 같다.
이 매커니즘을 유클리드 호제법이라고 하고,
구체적인 증명은 아래와 같다.
아래는 유클리드 호제법으로 개선된 재귀 알고리즘이다.
a가 b의 배수일 때, a%b가 0이 될 수 있음에 주의하자.
두 변수의 진행과정은 피보나치 수열과 같으므로, 시간 복잡도는 O( log(a+b) ) 이다.
시간복잡도 증명과정은 다음과 같다.
자, 전체 연산량이 선형 증가에서 로그 증가로 바뀌었다!
a = 1,000,000,000 이고 b = 876,543,210일 때, 평균 소요시간도 167 ns으로 줄었다.
(밀리 세컨드가 아니다, 무려 나노 세컨드다!)
하지만 재귀함수는 호출스택을 관리하는 오버헤드가 있으므로,
반복문으로 구현하여 성능을 더욱 향상시킬 수 있다.
평균 소요시간도 90 ns 로 줄었다.
다른 방법들도 자세하게 알고싶으면 다음 pdf 파일을 참고하자.
10-Gcd.pdf3개 이상일 때, 최대 공약수 구하기 |
간단하다. 예를들어 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 |
