[프로그래머스] LEVEL1 최대공약수와 최소공배수, python3

def solution(n, m):
    answer = []
    if n>m: # m is always bigger
        tmp=m
        m=n
        n=tmp
        
    tmp_big=m       #initial settings
    tmp_small=n
    gcd=tmp_big%tmp_small
    #최대 공약수, Euclid algorithm, m=n*i+x -> m'=n, n'=x -> 
    while (gcd):#나머지가 있으면
        tmp_big= tmp_small
        tmp_small=gcd
        gcd=tmp_big%tmp_small
    answer.append(tmp_small)
    #최소 공배수
    answer.append(n*m/(answer[0]))

    return answer

---

최대 공약수 구하는 알고리즘을 몰라서 하나씩 다 찾아보면서 해봤는데 통과할수 없었다.

그래서 찾아보니 유클리드 호제법(유클리드 알고리즘)이라고 하는 대단한게 있었다.

어릴때 배운거 같긴하지만

어쨌든 유클리드 호제법을 사용해서 풀어보니 바로 통과

 

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

 

다른 코드는 같은 유클리드 호제법이고 같은 알고리즘인데 파이썬 같이 작성한 코드이다