Euclidean algorithm(유클리드 호제법)

Euclidean Algorithm 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b, r)과 같게 되고 r이 0이 될때의 b의 값이 최대공약수가 된다. 일반적으로 쉽게 생각할 수 있는 최대공약수를 구하는 방법은 모든 자연수를 나눠보는 것이다. 하지만 이경우 시간복잡도는 O(n)이 된다. 다만 이 유클리드 호제법을 사용할 경우 O(logN)이 되어 더 빠른 속도를 나타낼 수 있다. Greatest Common Divisor(GCD) 2개의 자연수의 공통된 약수인 공약수 중 가장 큰 공약수가 최대공약수이다. 소스코드 ※ 아래 코드는 a>b 를 만족함을 가정 > C++ int gcd(int a,..