유클리드 알고리즘(최대공약수 GCD, 최소공배수 LCM) 구하기

GCD

최대공약수(Greatest Common Divisor)
: 둘 이상의 정수의 공약수 중에서 가장 큰 것

• 약수(Divisor): 주어진 수를 나누어 떨어지게 하는 수
• 공약수(Common Divisor): 둘 이상의 정수의 공통된 약수

구현방법

• 소인수분해 O(N)
• 유클리드 호제법 O(log N)

 

LCD

최소공배수(Lowest Common Multiple)
: 둘 이상의 정수의 공배수 중에서 가장 작은 것

• 배수(Multiple): 하나의 수에 정수를 곱한 수
• 공배수(Common Multiple): 둘 이상의 정수의 공통된 배수

 

math.gcd , math.lcm

기본으로 내장되어 있는 gcd, lcm 함수를 사용해도 된다.

• math 라이브러리에 속해 있어 import 필요

# math.gcd
import math

math.gcd(3) # 3 반환
math.gcd(3, 6) # 3 반환
math.gcd(3, 6, 9) #3 반환

# math.lcm
import math

math.lcm(2) # 2 반환
math.lcm(4, 8) # 8 반환
math.lcm(4, 8, 16) # 16 반환

 

유클리드 호제법

두 자연수의 최대공약수를 빠르게 구하는 알고리즘, 시간 복잡도 O(logN)

두 수 a와 b의 최대공약수를 구하고자 할 때,
1. a를 b로 나눈 나머지 구하기
2. 만약 나머지가 0 이라면, b가 최대공약수
3. 나머지가 0이 아니라면, a를 b로, b를 나머지로 바꾸어 이 과정을 반복

 

👩🏻‍💻최대공약수 GCD 구하기

 

1. while 반복문으로 구현

# while 반복문으로 구현

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

2. 재귀함수로 구현

반복문으로 구할 수 있으니, 재귀함수로도 구할 수 있음.

# 재귀함수로 구현

def gcd(a, b):
        if b == 0: # 종료 조건
                return a
        return gcd(b, a % b)

 

👩🏻‍💻 최소공배수 LCM 구하기

 

두 수의 곱을 최대공약수(GCD)로 나눈 값은 최소공배수(LCM)

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

• a, b의 곱이 음수일 경우 abs() 절댓값 구하는 함수를 이용해서 구현