46일차. 최대공약수와 최소공배수

링크

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

프로그래머스

 

문제

문제 설명

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

제한 사항

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

 

정답

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

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

def solution(n, m):
    return [gcd(n, m), lcm(n, m)]

 

풀이과정

a, b의 최대공약수는 유클리드 호제법에 의해 b와 a%b의 최대공약수와 동일하다. 그리고 a%b는 a보다 작으므로 점점 작아질 수 밖에 없다. 따라서, 재귀함수식으로 계속 줄여나가다가 a%b가 0이되어서 더이상 나눌 수 없게 될 때에는 b는 b로 나눠지고, a는 b로 나눠지므로, b가 최대공약수가 된다.

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

a, b의 최소공배수는 두 수의 곱을 최대공약수로 나누면 된다.

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

 

추가지식

이 문제를 풀기 위해선, 최대공약수와 최소공배수 간의 관계와, 유클리드 호제법이라는 지식이 있으면 쉽다.

물론 약수를 구하는 방법을 이용해서 생 노가다를 해도된다.

def gcd(a, b):
    result = 1
    a, b = min(a, b), max(a, b)
    for i in range(1, int(a**(1/2)+1)):
        if a%i==0:
            temp = a//i
            if b%i==0:
                result = max(result, i)
            if b%temp==0:
                result = max(result, temp)
    return result

하지만 유용한 수학 공식이 있다면 사용하는것이 좋기에 이번 기회에 배워보자.

최대공약수와 최소공배수 간의 관계

만약 n과 m의 최대공약수가 g라고 하자, 그렇다면 n과 m은 pg, qg (p,q는 서로소)로 바꿀 수 있다.

이 때, 최소공배수는 두 수에 가장 작은 공통 배수를 구해야한다.

n과 m의 공통적인 배수를 얻기 위해, pg와 qg에서 양쪽에 없는 p와 q를 각각에 곱해주면 나오는 pqg는 서로 공통적인 배수이면서, p와 q는 서로소이므로 이보다 작은 수를 곱하면 어느 한쪽의 배수가 될 수 없다. n과 m을 곱하면 p*q*g*g이므로, 최대공배수는 n*m/g가 된다.

유클리드 호제법

N과 M의 최대공약수를 gcd(n, m)이라고 하자, N을 M으로 나눈 몫이 Q고 나머지가 R이라고한다면, gcd(N, M)=gcd(M, R)이다. 귀류법으로 증명 가능하다.

만일 gcd(N, M)=gcd(M, R)가 아니라고하자, 

일단 N = MQ + R이다. 그리고 gcd(N, M)를 G라고한다면, N, M은 각각 pG, qG  (p,q는 서로소)로 변환 가능하다.

pG = qGQ + R이 될떄, 좌변의 q와 G가 정수이므로, 등식이 성립하려면 우변 역시 G의 배수여야한다. 따라서 R은 G의 배수이고, rG라고 나타낼 수 있다.

이때, N과 M의 최대공약수와 M과 R의 최대공약수가 달라야하므로, qG와 rG의 최대공약수는 G가 아니다. 따라서, q와 r은 서로소가 아니어야한다.

p = qQ + r (p,q는 서로소, q,r은 서로소가 아님)

q와 r이 각각 서로소가 아니므로 최대공약수 g를 가진다. 그러면 우변을 q'gQ+r'g로 바꿀 수 있다. 이는 g( q'Q+r )이므로, p는 g의 배수이고, p'g가된다. 그러나 p와 q는 서로소이므로 1 이외의 약수인 g를 가져서는 안된다. 따라서 g가 가능한 수는 1이므로 q와 r은 서로소이다. 즉, N과 M의 최대공약수와 M과 R의 최대공약수가 동일하다.

gcd(N, M)=gcd(M, R)