[알고리즘] 유클리드 호제법

유클리드 호제법이란?

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.
이 방법은 다음의 원리를 이용한다:

1. 두 수 a, b (a>b)가 있을 때, a를 b로 나눈 나머지를 r이라 하면,
   GCD(a,b)=GCD(b,r)과 같다.
2. 이를 반복하여 나머지가 0이 되는 순간, 나누는 수가 최대공약수이다.

 

유클리드 호제법의 과정 예시

예를 들어, 56과 98의 최대공약수를 구해보자.

1. 98÷56=198 \div 56 = 1 (몫), 나머지 42 → GCD(98, 56) = GCD(56, 42)
2. 56÷42=156 \div 42 = 1 (몫), 나머지 14 → GCD(56, 42) = GCD(42, 14)
3. 42÷14=342 \div 14 = 3 (몫), 나머지 0 → GCD(42, 14) = 14

따라서, 56과 98의 최대공약수는 14이다.

 

파이썬 코드 예제

1. 반복문을 이용한 방법

def gcd_iterative(a, b):
    while b:
        a, b = b, a % b
    return a

# 테스트
print(gcd_iterative(56, 98))  # 출력: 14

2. 재귀를 이용한 방법

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

# 테스트
print(gcd_recursive(56, 98))  # 출력: 14

3. Python 내장 함수 사용

import math

print(math.gcd(56, 98))  # 출력: 14

 

 

시간 복잡도

유클리드 호제법의 시간 복잡도는 **O(log(min(a, b)))**으로 매우 효율적이다.
나눗셈과 나머지 연산을 반복하므로, 숫자가 커질수록 연산 횟수는 로그 스케일로 증가한다.