유클리드 호제법은 두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.
말로 설명하자면 다음과 같다.
두 양의 정수 $a,b (a>b)$에 대하여 $a = bq + r (0 ≤ r < b)$이라 하면, $a, b$의 최대공약수는 $b,r$의 최대공약수와 같다. 즉,
$gcd(a, b) = gcd(b, r)$
$r = 0$이라면, $a, b$의 최대공약수는 $b$가 된다.
파이썬 코드로 나타내면 다음과 같다.
# 최대공약수
def gcd(a, b):
if b > a:
a, b = b, a
if a % b == 0:
return b
return gcd(b, a % b)
$O((log N)^2)$의 시간복잡도로 최대공약수를 구할 수 있다.
추가로 최소공배수 구하는 법도 알아보자면 최소공배수는 최대공약수를 안다면 아주 쉽게 구할 수 있다.
두 수를 곱한 값을 최대공약수로 나누면 된다.
# 최소공배수
def lcm(a,b):
return a * b // gcd(a, b)
파이썬의 math
라이브러리의 gcd
, lcm
함수를 이용하면 최대공약수와 최소공배수를 더 쉽게 구할 수 있다. 이 함수들은 2개 이상의 인자를 넣어도 최대공약수, 최소공배수를 구할 수 있다.
- 최대공약수 :
gcd()
- 함수에 아무것도 인자로 넘겨주지 않거나 모든 인자가 0인 경우에는 0을 출력한다.
- 최소공배수 :
lcm()
- 함수에 아무것도 인자로 넘겨주지 않으면 1을 출력한다.
- 모든 인자가 0인 경우에는 0을 출력한다.
import math
# 최대공약수
math.gcd() # 0
math.gcd(0, 0, 0, 0) # 0
math.gcd(2) # 2
math.gcd(2, 8) # 2
math.gcd(42, 56, 28) # 14
# 최소공배수
print(math.lcm()) # 1
print(math.lcm(0, 0, 0, 0)) # 0
print(math.lcm(2)) # 2
print(math.lcm(2, 8)) # 8
print(math.lcm(42, 56, 28)) # 168
[참고]
'CS > 알고리즘' 카테고리의 다른 글
피보나치 수열 (0) | 2023.02.10 |
---|---|
순열과 조합 (0) | 2023.02.10 |
에라토스테네스의 체 (소수 판별 알고리즘) (0) | 2023.02.05 |
효율적으로 약수 구하기 (0) | 2023.02.04 |
순열과 조합 (0) | 2021.08.10 |