유클리드 호제법 (최대공약수&최소공배수 구하기)

출처 - 나무위키 유클리드 호제법

 

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면

a와 b의 최대공약수(GCD)는 b와 r의 최대공약수(GCD)와 같다.

 

이 성질을 이용하여 다시 b를 r로 나눈 r' 를 구하고, 다시 r을 r'로 나누는 과정을 반복한다.

이 과정을 통해 r'가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다.

 

반복문을 활용한 유클리드 호제법

재귀를 활용한 유클리드 호제법

 

기존 이중 반복문을 통한 최대공약수 찾기는 O(min(a,b)) -> O(n) 의 시간복잡도를 가지고 있다.

하지만 유클리드 호제법을 이용하게 되면 나눗셈의 횟수가 log n 이므로 시간 복잡도는 O(log n)이다.

 

재귀를 통한 유클리드 호제법 사용시 공간복잡도가 나눗셈 횟수인 O(log N) 만큼 더 증가한다. 

Why? 호출 스택에서 나눗셈 횟수인 O(log N)만큼 공간을 잡아먹기 때문이다.

 

다른 알고리즘에서도 재귀보다는 사용시 반복문을 사용하는게 공간복잡도 측면에서 도움이 된다고 하는데 아직 그렇게까지 큰 수는 못만나봐서 모르겠다..

 

내장 함수가 있을까 하고 StackOverflow를 찾아본결과

#include <algorithm> 의 __gcd(int x, int y) 함수

#include <numeric> 의 __gcd(int x, int y) 함수가 있다.

 

내 Xcode에서는 둘 다 안된다..  스택오버플로우에도 gcd 내장함수에 관한 내용은 많지 않아서

그러면 gcd가 되려나 하고 호기심에 돌려보았는데 됐다..!

#include <numeric> 의 gcd(int x, int y) 함수 많이많이 알아갔으면 좋겠다.

gcd(int x, int y)가 되지 않으면 위의 __gcd() 써보자.

XCode 에서 Build한 결과 __gcd() 는 찾을 수 없다고 하여

#include<numeric>  의 gdc() 함수를 사용하였다.

 

최소공배수 구하기.

최소공배수 구하기는 어렵지 않다.

int x, y 가 주어졌을 때 최대공약수가 gcd(x,y) 라면

최소공배수는 x*y / gcd(x,y) 이다.

 

증명은 다음과 같다.

lcm 은 최소공배수, gcd는 최대공약수 이다.

 

간단.