프로그래머스 LV.1 - 최대공약수와 최소공배수[Python]

문제 설명

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

제한 사항

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

입출력 예nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

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

<풀이1>

유클리드 호제법

: 최대공약수를 구하는 알고리즘

• a와 b에 대해서(a<b) r=a%b이라고 하면, r==0이 될 때까지 b%r=r', r%r'을 했을 때 r'이 최대공약수이다.
• 최소공배수: (a*b)/최대공약수

import math

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 solution(n, m):
    a, b = sorted([n, m], reverse=True)
    r = 1
    while r > 0:
        r = a % b
        a, b = b, r
    answer = [a, n*m//a]
    return answer

<풀이3>

def solution(n, m):
    c, d = max(n, m), min(n, m)
    t = 1
    while t > 0:
        t = c % d
        c, d = d, t
    answer = [c, int(n*m/c)]

    return answer

<풀이4>

def solution(n, m):
    a = n
    b = m
    if n>m:
        n, m = m, n
    while m%n:
        r = m%n
        m = n
        n = r
    return [n, a*b/n]

풀이
1. a, b = n, m 중 최대 최소 값
2. (r = 나머지) r이 0일 때까지 : 유클리드 호제법
    - r = a%b
    - a, b = n, r
3. 두 수를 최대공약수로 나눈 값은 최소공배수
4. answer 리턴

 

 

 1. 유클리드 호제법

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.

정수 a, b, q r (b ≠ 0)에 대하여 a = bq + r,이면 G(a, b) = G(b, r)가 성립한다.

〈증명〉
G(a, b) = g라고 하자. 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다.
a = bq + r로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다.
G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다.

귀류법을 적용하여 결론을 부정해보자.
어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn= dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, q) = g가 성립한다.

 

나머지 ( % )

>>> 10%3

1

>>> 5%3

2