[프로그래머스-Level 1] 최대공약수와 최소공배수 ❌⭕

programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

---

def solution(n, m):
    if n > m:
        n, m = m, n
    
    for i in range(1, n+1):
        if n % i == 0 and m % i == 0:
            _max = i
    
    for i in range(m, n*m+1, 1):
        if i % n == 0 and i % m == 0:
            _min = i
            break
    
    return [_max, _min]

최대공약수는 n 의 약수이면서 m 의 약수인 수의 최댓값이다.

즉, n 과 m 을 미지수 i 로 나눴을 때 나머지가 0이 되는 수의 최댓값이다.

 

최소공배수는 n의 배수이면서 m의 배수인 수의 최솟값이다.

위 풀이에서는 m 부터 n*m 사이에서 n 과 m 으로 나누어 떨어지는 수를 찾았다.

---

def get_gcd(n, m):
    while m:
        n, m = m, n%m
        
    return n

def get_lcm(n, m):
    return n*m // get_gcd(n, m)

def solution(n, m):
    if n < m:
        n, m = m, n
    
    gcd = get_gcd(n, m)
    lcm = get_lcm(n, m)
    
    return [gcd, lcm]

유클리드 호제법을 이용한 풀이다.

GCD(Greatest Common Devisor)는 최대공약수, LCM(Least Common Multiple)은 최소공배수이다.

 

우선, GCD를 구하는 방법은 다음과 같다.

n 이 m 보다 크거나 같다고 가정했을 때,

n 을 m 으로 나눈 나머지를 r 이라고 하고 n 과 m 의 최대공약수를 (n, m) 으로 표현한다면 다음이 성립한다.

 

(n, m) = (m, r)

 

위 과정을 m이 0으로 될 때 까지 반복하면 최대공약수는 n 이 된다.

 

이제, LCM을 구할 차례다.

 

두 수 X 와 Y 가 있다고 가정해보자. X = AB, Y = BC 일 때, GCD = B, LCM = ABC 가 성립한다.

이 때 XY = AB**2C 이고 GCD = B 이므로, XY / GCD = LCM 이 성립한다.

 

LCM = n*m // GCD

 

이제, 이 알고리즘을 이용해 코드를 작성하면 된다.

나는 get_gcd, get_lcm 두 개의 함수를 작성해서 풀이했다.

---

def solution(n, m):
    x, y = max(n, m), min(n, m)
    
    while y:
        x, y = y, x%y
    
    return [x, n*m//x]

최대한 간결하게 풀어보았다.