[python] 여러개의 수에서 GCD, LCM 구하기

시험기간임에 OpenCV를 공부하기는 정상적으로 집중하기 힘들기에..

실시간 시스템을 공부하던중 여러 수의 LCM을 어떻게 구현할까에 대한 고민을 하였다.

15 와 20의 최소공배수는 직관적으로 60임을 알 수 있다.

또한 최대공약수는 5임을 역시 직관적으로 알 수 있다.

또한 우리는 이에 대한 알고리즘을 알고있다.

기존 GCD알고리즘

def GCD(a, b):

    if b > a:
        temp = a
        a = b
        b = temp

    while(b>0):
        temp = b
        b = a%b
        a = temp
    return a

별 다른 예외처리없이 구성된 GCD 알고리즘이다.

기존 LCM알고리즘

def LCM(a,b):

    gcd = GCD(a,b)
    a = a // gcd # 어차피 나누어 떨어지긴하는데 가독성상 명시적으로
    b = b // gcd
    return (gcd * a * b)

역시 별 다른 예외처리없이 구현하였다.

이를 args로 받아왔을 때 어떻게 구현할지에 대해

ex) 15, 20, 30이 들어왔다.

최대 공약수 구하기

1. 15와 20의 최대공약수를 구한다. = 5
2. 이 결과로 나온 5와 30의 최대공약수를 구한다 = 5
3. 끝

최소 공배수 구하기

1. 15 와 20의 최소공배수를 구한다. = 60
2. 60과 30의 최소공배수를 구한다. = 60
3. 끝

정말 간단한 것..

프로그램으로 구현할 때는 여기에 한 단계를 더 추가해주면된다

args로 한 엘리먼트씩 슬라이싱 하므로 맨 처음에는 GCD나 LCM이나 parameter가 1개씩밖에 못들어간다.

즉 파라미터가 1개일때는 어떻게 구할까?

1.  그냥 리턴해준다.
2. 끝

더욱 간단한 것..

즉, GCD와 LCM구현에서 a,b값을 받을때 b에 디폴트로 None을 넣어주고

b가 None이면 바로 a를 return해버리면 된다.

최종코드..

# -*- coding: utf-8 -*-



def GCD(a, b= None):
    if not b:
        return a

    if b > a:
        temp = a
        a = b
        b = temp

    while(b>0):
        temp = b
        b = a%b
        a = temp
    return a



def LCM(a,b=None):
    if b == None:
        return a

    gcd = GCD(a,b)
    a = a // gcd # 어차피 나누어 떨어지긴하는데 가독성상 명시적으로
    b = b // gcd
    return (gcd * a * b)

def LCMargs(*args):
    currentLCM = None
    for i in args:
        currentLCM = LCM(i, currentLCM)

    return currentLCM


def GCDargs(*args):
    currentGCD = None
    for i in args:
        currentGCD = GCD(i, currentGCD)
    return currentGCD

결과