[Algorithm] Euclidean algorithm GCD 유클리드 호제법 최대공약수
Euclidean algorithm 은 유클리드 호제법이라고도 하며,이 알고리즘으로 Greatest Common Divisor; GCD 최대공약수를 구할 수 있습니다.(GCD 를 응용해 Least Common Multiple; LCM 최소공배수도 구할 수 있어용) 유클리드 호제법 (GCD 최대공약수)두 양의 정수 a, b (a > b) 에 대하여, a = bq + r (0 a, b 의 최대공약수는 b, r 의 최대공약수와 같다. 즉,gcd(a, b) = gcd(b, r)r = 0 이라면, a, b 의 최대공약수는 b 가 된다. 쉽게 말하자면, 큰 놈과 작은 놈의 최대공약수는,큰놈 % 작은놈 = R 이라고 할 때, (큰놈을 작은놈으로 나눈 후 나머지를 R 이라고 할 때,)R 과 작은놈의 최대공약수와 같..
2025. 6. 15.
