📍문제

[프로그래머스] Lv.1 최대공약수와 최소공배수

---

✏️ 풀이

✔️ 유클리드 호제법

$a, b \in\mathbb{Z}$ 이고, $a$를 $b$로 나눈 나머지가 $r$이라고 하자. ($0 \leq r <b \leq a$)
$a$와 $b$의 최대공약수를 $(a, b)$라고 하면, $(a, b) = (b, r)$ 이다.

✔️ 두 수의 곱 = 최대공약수 x 최소공배수

• 최소공배수 = 두 수의 곱 $\div$ 최대공약수
• 최대공약수 = 두 수의 곱 $\div$ 최소공배수

---

💻 CODE

def solution(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. c, d = (a, b) 중 최대값, 최소값

2. 유클리드 호제법

• t = 나머지
• t가 0이 될 때까지

3. 최소공배수 = 두 수의 곱 $\div$ 최대공약수

---

🖥 다른 사람 풀이

def solution(n, m):
    gcd = lambda a,b : b if not a%b else gcd(b, a%b)
    lcm = lambda a,b : a*b//gcd(a,b)
    return [gcd(n, m), lcm(n, m)]

lambda 와 재귀함수를 이용하면 훨씬 간결하게 풀 수 있다는 사실을 알게 되었다.