Euclidean Algorithm

목차

• 유클리드 호제법 (Euclidean Algorithm)
• 확장 : GCD와 LCM의 관계
• math.gcd / math.lcm
• ✏️ 연습 문제

---

유클리드 호제법 (Euclidean Algorithm)

두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘

원리

두 수 a와 b 의 최대공약수는 a를 b로 나눈 나머지 r과 b의 최대공약수와 같습니다.

즉, GCD(a, b) = GCD(b, a % b)가 성립합니다.

 

💡나머지가 0이 될 때 탐색을 종료합니다

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

# 예제
print(gcd(48, 18))  # 출력: 6

⌛ 시간 복잡도

유클리드 호제법의 시간 복잡도는 a > b에 대해 최대 b의 자릿수와 비례합니다.

https://en.wikipedia.org/wiki/Euclidean_algorithm#Worst-case

Euclidean algorithm - Wikipedia

= O(Digit Length of b) = O(⌊log10​b⌋+1) = O(logb)

---

확장 : GCD와 LCM의 관계

GCD를 사용해 LCM을 구할 수 있다

두 수의 최소공배수(LCM, Least Common Multiple)는 두 수의 곱을 최대공약수로 나눈 값입니다.

def lcm(a, b):
    return (a * b) // gcd(a, b)

# 예제
print(lcm(48, 18))  # 출력: 144

---

math.gcd / math.lcm

Python의 math 모듈을 사용하면 직접 구현하지 않고도 GCD와 LCM을 쉽게 구할 수 있습니다.

https://docs.python.org/3/library/math.html#math.gcd

math — Mathematical functions

https://docs.python.org/3/library/math.html#math.lcm

math — Mathematical functions

 

from math import gcd, lcm

gcd(48, 18) # 출력: 6
lcm(48, 18) # 출력: 144

 

⚠️ gcd는 Python 3.5부터, lcm은 Python 3.9부터 사용 가능합니다.

---

✏️ 연습 문제

Bronze I : BOJ 02609, 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

💡두 수의 관계를 이용해, GCD와 LCM을 각각 계산해보세요.

 

 

Gold V : BOJ 02436, 공약수

https://www.acmicpc.net/problem/2436

💡두 수 A, B에 대해 모든 경우의 수를 고려하는 것은 비효율적입니다. GCD를 사용해 범위를 줄여보세요.