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

[프로그래머스] 최대공약수와 최소공배수 / 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]을 리턴해야 합니다.

😃 나의 풀이

def gcd(a, b):
    if a < b:
        (a, b) = (b, a)
    while b != 0:
        (a, b) = (b, a % b)
    return a
 
def solution(n, m):
    return [gcd(n,m), n*m/gcd(n,m)]

해당 문제는 크게 어렵지 않지만, Python을 이용한 알고리즘 문제 해결 과정에서 최대공약수를 구해야하는 경우에 유클리드 호제법을 이용하여 쉽게 최대공약수를 구하는 방법을 소개하고자 풀이를 적습니다. 유클리드 호제법은 a가 항상 크게 해주고, a와 b의 최대공약수는 b와 a를 b로 나눈 나머지와의 최대공약수와 같기 때문에 나머지가 0이 될때까지 이 작업을 반복해줍니다. 나머지 b가 0일 때의 a값이 a, b의 최대공약수가 됩니다. 추가적으로 최대공약수를 구하면, 최소공배수는 a, b의 곱을 최대공약수로 나눈 값이 됩니다.