2019-01-30-AT-gcdlcm.md

2019년 1월 30일

Lv1 - 최대공약수 최소공배수 {docsify-ignore-all}

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

문제

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

제한사항

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

풀이

# 방법1
def gcdlcm(a, b):

    G = 1
    range_num = min(a,b) # 둘 중 작은 수 까지의 범위만 구하면 된다.
    for i in range(range_num, 1, -1):
        if(a%i ==0 and b%i ==0 ):
            G = i
            break

    L = int(a*b/G)
    return [G, L] # [G, L], 최대공약수, 최소공배수

다른 사람 풀이

# 방법2 (유클리드 호제법)
'''
a를 b로 나눈 나머지가 r이라고 하자(a>=b, 0<=r<b)
a와b의 최대공약를 (a,b)라고 하면 다음이 성립한다.
(a,b) = (b,r)

ex) (1071,1029) = (1029,42) = (42,21) = (21,0) = 21
'''
def gcdlcm(n,m):

    a = max(n,m)
    b = min(n,m)

    remainder = a%b
    while(remainder>0):
        a = b
        b = remainder
        remainder = a%b

    G = b
    L = int(n*m/G)
    return [G,L]

배운점

• a,b의 최소공배수 = a*b/G (G = a,b의 최대공약수)
• 유클리드 호제법으로 최대공약수를 빠르고 효율적으로 구하는 법을 알게되었다.

느낀점

• 다른 사람의 풀이를 보며 좀 더 효율적인 방법을 알아가는 재미가 있다.