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

유클리드 호제법

• 2개의 자연수의 최대공약수를 구하는 알고리즘
• 두 개의 자연수 a와 b에서(a>b) a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다"라는 원리를 이용한 알고리즘

구현

재귀함수 활용

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

반복문 활용

def GCD(a, b):
	while b > 0:
        a, b = b, a % b
    return a

다향식일 경우

a = 8
b = 16
c = 24

result = GCD(a, b) // a와 b의 최대공약수 -> result
result = GCD(result, c) // a와 b의 최대공약수 result와 c의 최대공양ㄱ수

print(result)

1. GCD를 구하는 함수를 먼저 구현
2. a와 b의 최대공약수를 먼저 계산
3. 계산된 최대공약수와 c의 최대공약수를 구함

• 다향식일 경우 위의 순차적인 방식으로 최대공약수를 구할 수 있음

장점

• 빠르다
  • 일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법이 있는데 이 경우 모든 정수를 나눠야 하므로 시간 복잡도는 O(N)이 됨.
  • 유클리드 호제법을 사용한다면 비교대상의 두 수 a와 b에서 a를 b로 나눈 나머지를 r이라고 했을 때 a%r이 0이 될 때까지 반복을 해주는 방식으로 최대공약수를 구하므로 시간 복잡도를 O(logN) 으로 줄일 수 있음

단점

• 최대공약수는 빠르게 산출이 가능하지만 최소공배수를 구할 때는 비교 대상의 초기값 a와 b를 특정 변수에 저장을 하고 있어야 함

최소 공배수 구하기

def LCM(a, b)
	return a * b // GCD(a, b)

출처
https://coding-factory.tistory.com/599