최대공약수와 최소공배수

문제

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

 

제한 사항 

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

 

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

---

풀이

1. Me

def solution(n, m):
    if n > m:
        n, m = m, n
    
    tmp = [i for i in range(1, n + 1) if n % i == 0]
    min = [tmp[i-1] for i in range(1, len(tmp) + 1) if m % tmp[i-1] == 0][-1]
    max = [i for i in range(n, 10000000, n) if i in range(m, 10000000,m)][0]
    return [min, max]

이 문제는 어렵게 다가왔던 문제들 중 하나였다. 

 

우선 n 과 m의 대소가 명시되어 있지 않았기에, n이 항상 m보다 작도록 만들어 주었다. m의 약수에 해당하는 n의 약수 중 가장 큰 약수를 찾으면 그것은 최대공약수다. n의 약수들을 모아놓은 리스트를 만들고 이를 활용하여 최대공약수를 구하였다. 이후 최대공배수를 찾기 시작했다. 만들어놓은 리스트를 활용하고 싶었지만 방법이 떠오르지 않았고, 결국 각각의 수들에 대해 최대값이 10000000인 (문제의 제한조건 범위) 배수 리스트를 만들어 최소공배수를 찾는 방법으로 문제를 풀었다. 

 

2. Others

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

유클리드 호제법을 이용해 문제를 푸셨다. 

변수 t에는 입력받은 두 수 중 큰 수(c)를 작은 수(d)로 나눈 나머지를 저장했고, 이후 c에는 d 값을, d 에는 t 값을 저장하였다. 이 작업을 t가 0보다 큰 동안 반복했다. 근데 지금봐도 왜 저렇게 수행할 경우 c = 최소공배수, int(a*b/c) 가 최대공약수가 되는지 이해가 가지 않는다. 유클리디안 호제법을 공부해야 이해갈 것 같은 느낌적인 느낌. (맨 밑에 자료 추가)

# 최대공약수
def gcd(a, b):
    if a < b:
        a, b = b, a 
        
    return b if a % b == 0 else gcd(b, a % b)

# 최소공배수
def lcm(a, b):
    return int(a * b / gcd(a, b))

def gcdlcm(a, b):
    return [gcd(a,b), lcm(a, b)]

이 분은 gcd 함수와 lcm 함수를 따로 구현하여 문제를 푸셨다. 나에게는 이 코드가 좀 더 이해하기 쉽게 다가왔지만, 그래도 여전히 int(a * b / gcd(a, b)) -> 이 부분이 이해 안 되긴 한다. 

 

* a와 b를 곱하고, 이를 a와 b의 최대공약수로 나누면 최대공배수가 되나 보다. 

---

개념 정리

1. 유클리드 호제법

-> 유클리드 호제법이란 두 수의 최대공약수를 구하는 알고리즘으로, 유클리드에 의해 기원전 300년경 발견된 가장 오래된 알고리즘이다.

 

1) 동작과정 

· 큰 수(a)를 작은 수(b)로 나눈 나머지(c)를 구한다. 

· 나눴던 수(b)를 나머지(c)로 나누어 다시 나머지(d)를 구한다.

· 이 과정을 계속 반복한다 

· 나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 값이 a 와 b의 최대공약수가 된다. 

 

* 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘 

 

2) 참고

· 추가적인 정보를 알고 싶다면, 여기를 참고하자