[Python] 프로그래머스 - Level1 - 최대공약수와 최대공배수

def solution(n, m):
    # 최대공약수
    n_gcd = [i for i in range(1, n+1) if n % i == 0]
    m_gcd = [i for i in range(1, m+1) if m % i == 0]
    for i in m_gcd[::-1]:
        if i in n_gcd:
            gcd = i
            break
        
    # 최소공배수
    n_lcm = [i for i in range(n, n*m+1, n)]
    m_lcm = [i for i in range(m, n*m+1, m)]
    for i in m_lcm:
        if i in n_lcm:
            lcm = i
            break
    return gcd, lcm

좀 오래 걸리긴 했는데 그래도 혼자 해결해서 다행이다.
효율적이진 못한 것 같아서 풀고 타인 코드도 확인함

타인코드

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

유클리드 호제법을 사용했다고 함

유클리드 호제법
1. 두 수 $n$과 $m$에 대해 $n \times m = (최대공약수) \times (최소공배수)$ 성립
2. 따라서, 최대공약수를 먼저 구하고, 위 식을 이용해서 최소공배수를 도출함

이걸로 프로그래머스 Level1 올 클리어!