최대공약수와 최소공배수

[문제]

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

[제한 사항]

두 수는 1이상 1,000,000이하의 자연수입니다.

 

[풀이]

def solution(n, m):
    n_list = []
    
    # 최대공약수 찾는 과정
    for i in range(n, 0, -1):
        if (n % i == 0) and (m % i == 0):
            n_list.append(i)
    
    a = max(n_list)
    b = max(n_list) * (n // max(n_list)) * (m // max(n_list))
    
    answer = [a, b]
    
    return answer

최소공배수는 각 수를 최대공약수로 나눈 값을 최대공약수와 곱하면 나온다는 특성을 활용하여 풀이

 

[더 나은 풀이]

def gcdlcm(a, b):
    c,d = max(a, b), min(a, b)
    t = 1
    while t>0:
        t = c%d
        c, d = d, t
    answer = [ c, int (a*b/c)]
    return answer

두 정수의 최대공약수를 구하는 알고리즘인 유클리드 호제법에 관한 코드이다.

• c를 d로 나누었을 때의 나머지를 t라고 한다면, t = 0일 때 c가 최대공약수
• 따라서 t = 0일때까지 반복적으로 수행