유클리드호제법

유클리드 호제법?

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 방법 중 하나입니다.

유클리드 호제법은 나눗셈과 나머지를 이용하여 반복적으로 계산하여 GCD를 구하는 매우 효율적인 알고리즘으로, 시간 복잡도는 O(log(min(a, b)))입니다.

---

알고리즘 설명

유클리드 호제법은 다음 규칙을 기반으로 동작합니다:

1. 두 수 a와 b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라고 합니다.
2. 이제 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.
3. 이 과정을 r이 0이 될 때까지 반복합니다. 이때 나머지가 0이 되면, b가 바로 최대공약수(GCD)입니다.

---

구현 코드

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a