유클리드 호제법

유클리드 호제법에 대해 알아보자.

유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다.

일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법은 더 간단한 방식으로 구할 수 있다.

유클리드 호제법의 핵심 이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다.

MOD 연산이란?

두 값을 나눈 나머지를 구하는 연산이다.
ex)

10 MOD 4 = 2 # 10 % 4 = 2

MOD 연산을 이용하여 유클리드 호제법을 구현해보자.

MOD 연산으로 구현하는 유클리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 2단계를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

ex) 270 과 192의 최대공약수

gcd(270, 192)

270 % 192 = 78
	  192 % 78 = 36
		    78 % 36 = 6
				 36 % 6 = 0
				gcd(270, 192) = 6

이와 같은 방식으로 270과 192의 최대공약수는 6이다.
이러한 알고리즘을 코드로 나타내면 다음과 같다.

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

그럼 이제,
유클리드 호제법을 활용하여 최소공배수를 구해보자.

---

최소 공배수 - 백준 1934번

백준 - 최소공배수

예제 입력1

3
1 45000
6 10
13 17

예제 출력1

45000
30
221

풀이

최소 공배수는 A와 B가 주어졌을 때,
A * B / (A와 B의 최대공약수)로 구할 수 있다.

코드

def gcd(a, b): # 최대공약수 구하기
	if b == 0:
    	return a
    else:
    	return gcd(b, a%b)

t = int(input())

for i in range(t):
	a, b = map(int, input().split())
    result = a * b / gcd(a, b) # 최소공배수
    print(int(result))

---

최대 공약수 - 백준 1850번

백준 - 최대공약수

예제 입력1

500000000000000000 500000000000000002

예제 출력1

11

풀이

예제 입력1과 같이 입력값이 크면 단순한 방법으로 최대 공약수를 찾을 수 없다. => 유클리드 호제법 사용!

풀이 순서

1. A와 B의 최대공약수를 구한다.
2. 1에서 구한 최대공약수의 길이 만큼 1을 출력한다.

ex)

500000000000000002 % 500000000000000000 = 2
					 500000000000000000 % 2 = 0

500000000000000002와 500000000000000000의 최대공약수는 2로,
최대공약수의 길이만큼 1을 반복해서 출력 -> 11

코드

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

a, b = map(int, input().split())
result = gcd(a, b)

while result > 0: # result값만큼 반복하여 1 증가
	print(1, end='')
    result -=1

정리하며

유클리드 호제법 알고리즘을 활용하여 최대공약수와 최소공배수를 구하는 방법을 알아봤다!
까먹지 말고 잘 사용하자.