#18 알고리즘 연습 - 최대공약수와 최소공배수(Python)
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
| n | m | return |
|---|---|---|
| 3 | 12 | [3, 12] |
| 2 | 5 | [1, 10] |
입출력 예 설명
입출력 예 #1 위의 설명과 같습니다.
입출력 예 #2 자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
문제풀이
최대공약수와 최소공배수의 특징에 대해서 생각을 해보았는데 최대공약수의 경우 두 수의 공약수중에 느낌으로 찾았고 최대 공배수도 두 수를 비교하여 느낌적으로 찾아서 실제로 그 느낌으로 코드를 짜기는 어려웠다
그래서 나온게 첫번째 코드인데 두 수중 1개의 숫자에 대해 약수list를 만든다음 큰 약수부터 차례차례 다른 수를 나눌 수 있는지 체크해주고
최소공배수는 최악의 경우 두 숫자끼리 서로의 곱이 최소공배수가 되므로 다른 한 숫자보다 작은 범위에서 곱 연산을 진행해 결과가 다른 한숫자의 배수인지 확인해주는 절차를 거쳤다
이 외에도 소인수분해를 해서 최소공배수 최대공약수를 구하려는 방법도 구상해봤지만 해당 과정안에서 반복문이 너무 많이 들어가서 연산 속도가 저하될 것 같은 생각에 사용하지 않았다.
내 풀이 🏆
def solution(n, m):
answer = []
if m % n == 0: #이 연산의 가정은 m이 n보다 큰수이다를 가정했다.
return [n,m] 그럼 최대공약수, 최소공배수 모두 서로가 되므로 그냥 return
else:
temp = [i for i in range(1,n+1) if n%i == 0] #위에서 n을 더 작은 숫자로 가정했으니 n의 약수들의 list를 만든다
while len(temp)>0:
tempele = temp.pop() #list의 뒷부분일수록 큰 약수가 위치해 있으므로 최.대 공약수를 찾기위해서는
if m % tempele == 0: 뒤에서 부터 pop을 해준다
answer.append(tempele)
break #찾으면 break를 통해서 반복문을 탈출
for i in range(1,n+1): #최소공배수를 찾기 위해서 다른 숫자보다 작은 자연수들을 차례차례 곱해서 결과가
if i*m % n ==0: 다른 숫자의 배수인지 확인해준다
answer.append(i*m)
break
return answer다른 풀이🏆(최소공약수 알고리즘)
def solution(n, m):
def gcd(n,m): #이 알고리즘에서는 유클리드 호제법을 사용하여 계산
while(m): #여기서는 m이 나중에 나머지의 포지션을 잡으므로 m의 유무에 따라 반복을 설정해주자
n,m = m,n%m #유클리드 호제법에서 두번째 인자에는 나머지가 들어간다
return n
return [gcd(n,m), n*m/gcd(n,m)]
#해당 값은 최대공약수, 그리고 최소공배수*최대공약수가 n*m임을 이용해줬다알고 넘어가야할 것
유클리드 호제법에 대해 정수론 시간에 배웠었는데 실생활에서의 활용예제를 못 보다가 막상 마주치니까 떠오르지 않았다 하지만 이를 코드로 구현하니 정말 간결하고 빠르게 gcd 가 구해지는 것을 알수 있다.
유클리드 호제법의 예시
180 ＝ 108×1 + 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2위의 예시를 보면 알수 있듯 // 이런 방향으로 애들이 착착 내려오는 것을 알수 있다. 따라서 n,m에서 m, n%m 이 되고 이게 계속 반복되다가 n,0 이 되면 n이 m으로 나눠떨어진다는 의미이므로 해당 값이 최대공약수가 된다
최소공배수는 n*m/gcd()에 대해서는 소인수분해에서 최소공배수와 최대공약수 구하는 부분에서 알수 있는 성질이다
42 = 3^2 * 7^1
15 = 3^1 * 5^1최대공약수 = 공통으로 가지고 있는 소수 3^1 최소공배수 = 3^2 * 7^1 * 5^1 (공통으로 가진 소수는 최대 차수)
따라서 우리는 최대공약수 * 최소공배수 = A * B임을 알수 있다.