Algorithmic Wisdom 🧠/Dynamic1 [알고리즘][재귀] - 유클리드 알고리즘 (Euclidean algorithm) 최대공약수(Greatest common divisor)란? "0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다." 최대공약수를 구하는 가장 대표적인 방법 (소인수분해와 나눗셈을 이용하는 방법)은 소인수분해 원리에 기반을 두기에, 정수의 크기가 커질수록 직접 소인수분해 하기엔 부담이 된다. 이때 효과적인 방법은 나눗셈 정리에 기반을 둔 유클리드 호제법을 사용하는 것이다. 유클리드 호제법이란(Euclidean algorithm)? "2개의 자연수 또는 정식의 최대공약수를 구하는 인류 최초의 알고리즘이다." 두 양의 정수 a , b (a < b)에 대하여 a = b * q + r (0≤ r < b)이라 하면, a , b 의 최대공약수는 b , r 의 최대공약수와 같다. 즉 gcd(a , b.. 2023. 7. 8. 이전 1 다음 728x90 반응형
