[프로그래머스] 최대공약수와 최소공배수 (Python)

문제 설명

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

제한 사항

두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

• 입출력 예 #1
  위의 설명과 같습니다.
• 입출력 예 #2
  자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘

두 정수가 n과 m이고, n을 m으로 나눈 나머지가 r일 때, n과 m의 최대공약수는 m과 r의 최대공약수와 같다.

위의 과정을 나머지(n % m)가 0이 될 때까지 반복하면 된다.

예를 들어 12와 15의 최대공약수를 손으로 구해 보자.

• GCD(12, 15) = GCD(15, 12 % 15) = GCD(15, 12)
• GCD(15, 12) = GCD(12, 15 % 12) = GCD(12, 3)
• GCD(3, 12 % 3) = GCD(3, 0)

따라서 GCD는 3이다.

gcd 함수를 재귀로 구현하기

위의 내용 그대로 만들면 아래와 같다.

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

gcd 함수를 반복문으로 구현하기

def gcd(n, m):
    while m > 0:
        n, m = m, n % m
    return n

lcm 함수 구현하기

두 수 n과 m의 최대공약수를 GCD라고 할 때, 다음 관계식이 성립한다.

• n = GCD × a, m = GCD × b (a와 b는 몫)
• LCM = GCD × a × b
• LCM = n × m / GCD

def lcm(n, m):  
    return n // gcd(n, m) * m

출처: https://wikidocs.net/188224

---

정답 풀이1 (하나씩 나눠보는 방법)

def solution(n, m):
    # 최대 공약수 구하기
    for i in range(min(n, m), 0, -1):
        if (n % i == 0) and (m % i == 0):
            a = i
            break
    # 최소 공배수 구하기        
    for j in range(max(n, m), (n * m) + 1):
        if j % n == 0 and j % m == 0:
            b = j
            break
        
    return [a, b]

정답 풀이2 (유클리드호제법)

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

정답 풀이3 (유클리드호제법)

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)

def lcm(a, b):
    return int(a * b / gcd(a, b))


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

    return answer

• 같은 풀이 (람다사용)

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)]

정답 풀이4 (import math)

• 프로그래머스 문제풀이에서는 math.lcm 사용이 불가능했다.
• lcm함수를 사용하기 위해서는 파이썬 3.9 이상의 버전으로 업그레이드가 되어야 한다.
  
• 따라서 gcd만 사용하고 lcm은 직접 코딩하도록 한다.

import math
def solution(n, m):
    gcd = math.gcd(n, m)
    return [gcd, int(n * m / gcd)]

최대공약수 : math.gcd(숫자)

: 둘 이상의 정수의 공약수 중에서 가장 큰 것

import math
math.gcd(3) # 3 반환
math.gcd(3, 6) # 3 반환
math.gcd(66, 22, 11) # 11 반환

최소공배수 : math.lcm(숫자) * v3.9이상

: 둘 이상의 정수의 공배수 중에서 가장 작은 것

import math
math.lcm(2) # 2 반환
math.lcm(2, 4) # 4 반환
math.lcm(66, 22, 11) # 66 반환

출처: https://blockdmask.tistory.com/525