[알고리즘] 유클리드 호제법 - 최대공약수(GCD) 계산

유클리드 호제법

두 자연수 A, B (A > B)에 대하여 A를 B로 나눈 나머지를 R이라고 한다면,
이 때 A와 B의 최대공약수(GCD)는 B와 R의 최대공약수와 같다.

이 과정을 반복하여 나머지가 0이 될 때 나누는 수가 최대공약수가 된다.

코드 구현 (Python)

# 유클리드 호제법을 이용한 최대공약수(GCD) 계산

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

# 예제 실행
a, b = 48, 18
print(f"{a}와 {b}의 최대공약수: {gcd(a, b)}")

예제 설명

1. 48 ÷ 18 = 2 (몫), 48 % 18 = 12 (나머지)
2. 18 ÷ 12 = 1, 18 % 12 = 6
3. 12 ÷ 6 = 2, 12 % 6 = 0
4. 나머지가 0이므로, 최대공약수는 6

시간 복잡도

• 유클리드 호제법의 시간 복잡도는 O(log N)으로 매우 효율적이다.