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

수학이랑 친해지기

최대공약수는 말 그대로 두 수의 공약수 중 최댓값을 의미한다.

두 수의 약수를 모두 구하고 공통된 약수 중 최댓값을 구하면 될 것이다.

 

하지만 위 과정은 뭔가 비효율적이다.

 

유클리드 호제법을 이용한다면 최대공약수를 간단하게 구할 수 있다

 

유클리드 호제법 - 최대공약수

호제법은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

흐름은 다음과 같다.

두 수 A와 B가 있을 때 (A > B) A 를 B로 나눈 나머지가 존재하지 않을 때 까지 A % B 연산을 계속한다.

A % B  = C (C != 0)

B % C = D (D != 0)

C % D == 0 일 경우 D는 A와 B의 최대공약수다.

 

이 과정을 유클리드 호제법이라고 한다.

 

TMI) 최대 공약수를 구하는 함수의 이름을 gcd() 라고 많이 짓는데 최대공약수가 영어로 Greatest Common Divisor 이기 때문이다.

 

유클리드 호제법 - 최소공배수

최소공배수는 말 그대로 두 수가 가지는 공배수 중 최솟값이다.

 

최소공배수는 두 수를 최대공약수로 나눈 값이다.

때문에 두 수를 곱한 값을 위에서 유클리드 호제법으로 구한 최대공약수로 나눠주면 최소공배수를 구할 수 있다.

 

TMI) 최소공배수는Least Common Multiple이기 때문에 lcm() 이라고 많이 사용한다.

 

코드

def solution(n, m):
    answer = []
    a = max(n, m)
    b = min(n, m)

    while(b):
        c = b
        b = a % b
        a = c

    return [a, n*m // a]