[Level1] 최대공약수와 최소공배수 (gcdlcm)

1. 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 gcdlcm(3,12) 가 입력되면, [3, 12]를 반환해주면 됩니다.

2. 풀이

- 풀이에 앞서 최대공약수를 구하는 방법인 유클리드 호제법에 대해 공부해 보자

1) 유클리드 호제법 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q r (b ≠ 0)에 대하여 a = bq + r,이면 G(a, b) = G(b, r)가 성립한다. 〈증명〉 G(a, b) = g라고 하자. 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다. a = bq + r로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다. G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다. 귀류법을 적용하여 결론을 부정해보자. 어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn= dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, q) = g가 성립한다. [네이버 지식백과] 유클리드 호제법 (통합논술 개념어 사전, 2007. 12. 15., 청서출판)

1) 내가 작성한(?) 코드

- 이번 문제를 풀면서 아직 많이 부족하다는 것을 다시 한번 느끼게 되었다. 

def gcdlcm(a, b):
    answer = []

    tmp = a
    tmp2 = b

    if b>a:
        tmp = a
        a = b
        b = tmp
        tmp2 = a

    mod = a%b

    while mod>0:
        a = b
        b = mod
        mod = a%b

    answer.append(b)

    if b==1:
        answer.append(tmp*tmp2)
    elif b>1:
        answer.append(int(b*tmp/b*tmp2/b))   

    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

2) 다른 풀이

① 재귀함수를 사용하여 해결 하였다. 

def gcdlcm(a, b):
    def _gcd(x,y):
        if y==0: return x
        return _gcd(y,x%y)
    g = _gcd(a,b)
    return [ g, a*b//g ] # '//' 은 나눗셈의 몫

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

② 간단한 해결 방법

def gcdlcm(a, b):
    c, d = max(a, b), min(a, b)
    t = 1
    while t > 0:
        t = c % d
        c, d = d, t
    answer = [c, int(a*b/c)]

    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))