[프로그래머스] Level1 | 최대공약수와 최소공배수 - 파이썬(Python) | 연습문제

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

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

프로그래머스 레벨1에 있는 최대공약수와 최고공배수 구하는 문제를 풀었다.

---

처음 문제를 보고 2개의 for문을 사용해서 최소 공배수와 최대 공약수를 n,m별로 구해야하나 생각을 했는데 그렇게 되면 시간 복잡도가 굉장히 비효율적일 것 같아서 다른 방법을 찾아봤다.

 

찾아보니까 최대공약수는 유클리드 호제법이라는 알고리즘으로 구할 수 있었다.

유클리드 호제법은 n,m의 숫자가 주어질 때 n과 m의 최대 공약수는 (n을 m으로 나눈 나머지)와 (m의 최대 공약수)가 같다는 것을 의미한다.

큰 수를 작은 수로 나눠 구한 나머지로 큰 수를 대체하고 큰 수를 작은 수로 계속 나누면서 나누어 떨어질 때 까지 반복한다. 나머지가 0이 되어 나누어 떨어지면 나누는 수가 최대공약수가 되는 것이다.

최대공약수 코드

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

 

 

최소공배수 또한 비효율적으로 for문을 사용하는 것이 아니라 간단하게 최대공약수를 사용하여 구할 수 있었다.

n,m의 배수 중 공통 배수 중 가장 작은 값이 최소공배수이며,

최소공배수는 n,m의 곱을 n,m의 최대공약수로 나누어서 구할 수 있다.

최소공배수 코드

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

 

 

이렇게 각각 함수로 구현을 한 뒤 최종 solution 함수를 작성하면 아래와 같다.

정답 코드

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


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

def solution(n,m) :
    answer = []
    answer.append(gcd(n,m))
    answer.append(lcm(n,m))
    
    return answer

answer에 gcd 함수로 구한 최대공약수와 lcm 함수로 구한 최소공배수를 append 해주었다.

 

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비