최대공약수(GCD), 최소 공배수(LCM) 구하기

서론

프로그래머스 문제 중 멀쩡한 사각형을 풀다가 1시간만에 최대 공약수를 사용해 문제를 해결했다. 최대 공약수와 최소 공배수의 개념은 알지만 직접 구현해 본적은 없어 이번에 Python으로 직접 구현해보게 되었다.

최대 공약수(GCD) : 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미한다.

Brute force로 구하는 방법

두 자연수 중 작은 자연수를 선택하고 1부터 작은 자연수까지의 모든 수로
두 수를 나누다 동시에 나누어 떨어지는 가장 큰 수를 구한다.
시간복잡도 : O(N)

# Brute Force Algorithm
def get_gcd(a, b):
    min_num = min(a, b)
    for i in range(1, min_num+1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

유클리드 호제법으로 구하는 방법

두 방법 모두 a를 b로 나눈 나머지를 n이라고 할 때(단, a > b) a와 b의 최대 공약수는
b와 r의 최대 공약수와 같다는 성질을 이용한다.
O(logN)의 시간복잡도를 가져 Brute force Alogrithm의 시간복잡도 O(N)보다 효율적이다.

유클리드 호제법은 두 가지 접근 방법이 있다.
1. 반복문을 이용한 방법
2. 재귀를 이용한 방법

먼저 반복문을 이용한 방법을 보면

# Euclidean Algorithm Using Loops
def get_gcd_using_EA_loops(a, b):
    # a를 큰 값으로 두기 위한 코드
    if a < b:
        tmp = a
        a = b
        b = tmp
        
    # a%b를 반복하며 b가 0이 될때까지 실행하고 b가 0인 순간의 a를 GCD로 판단하고 반환한다.
    while a != 0:
        n = a % b
        a = b
        b = n

    return a

다음으로 재귀를 이용한 방법을 보면

# Euclidean Algorithm Using Recursion
def get_gcd_using_EA_recursion(a, b):
    if a % b == 0:
        return b
    else:
        return get_gcd_using_EA_recursion(b, a % b)

Python math 모듈 사용하기

사실 가장 간단한 방법은 Python의 math 모듈의 gcd 함수를 사용하는 것이다.
단, gcd 함수의 경우 Python 3.5버전부터 사용이 가능하다.

import math
# a, b는 임의의 두 자연수
math.gcd(a, b)

최소 공배수(LCM) : 두 자연수의 공통된 배수 중에서 가장 작은 수

공식 사용하기

최소 공배수 = 두 자연수의 곱 / 최대 공약수 (LCM = a * b / GCD)

def get_lcm(a, b):
    return int(a * b / get_gcd_using_EA_recursion(a, b))

Python math 모듈 사용하기

사실 가장 간단한 방법은 Python의 math 모듈의 lcm 함수를 사용하는 것이다.
단, lcm 함수의 경우 Python 3.9버전부터 사용이 가능하다.

import math
# a, b는 임의의 두 자연수
math.lcm(a, b)