[자료구조 멘토링] 유클리드 호제법을 이용한 최소 공배수, 최대 공약수 (feat.Python)

유클리드 호제법은 두 정수의 최대 공약수(GCD)를 구하는 효율적인 알고리즘이다.

 

기본 아이디어

최대 공약수

두 수 a와 b가 주어졌을때, a를 b로 나눈 나머지를 r이라고 정의 ( a와 b의 공약수는 b와 r의 공약수와 동일하기 때문 )

a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다  ( a와 b의 최대 공약수 == b와 r의 최대 공약수 )

즉, gcd(a, b) == gcd(b, r)이라는 식이 만들어진다.

b = 0이 되면 최대 공약수가 된다.

 

예를 들어, a = 48 과 b = 18이라고 생각해보자.

gcd(48, 18) = gcd(18, 12) 

gcd(18, 12) = gcd(12, 6)

gcd(12 , 6) = gcd(6, 0)

gcd(6, 0) = 6   (b가 0이 되었으므로, 최대 공약수는 6이 된다.)

 

왜 b가 0이 되면 최대 공약수일까?

a를 b로 나눈 나머지 r이 0이 되면, 그 순간은 b가 a를 완전히 나눴다는 뜻이다.

gcd(a, 0)은 0은 모든 수로 나눌 수 있으므로, a의 모든 약수도 0으로 나눌 수 있다.

따라서 a와 0의 최대 공약수는 a이고, 그래서 gcd(a,0) = a 가 된다.

 

최소 공배수

최소배수는 아래와 같은 식을 이용하여 구할 수 있다.

lcm(a,b)= a×b​ / ​gcd(a,b)

 

 

 

 

 

 

 

 

 

 

 

 

 

코드 예제

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

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

# 예제 실행
a, b = 48, 18
print("최대공약수:", gcd(a, b))  # 출력: 최대공약수: 6
print("최소공배수:", lcm(a, b))  # 출력: 최소공배수: 144