💡 문제
N개의 최소공배수
유형연습문제
문제 설명두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 조건
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
입력
- ex1) [2, 6, 8, 14]
- ex2) [1, 2, 3]
출력
- ex1) 168
- ex2) 6
✍🏻 풀이
SOL 1
# SOL 1)
# 2개 수의 최소공배수 구하는 함수
def least(a, b):
A, B = a, b
while b > 0:
a, b = b, a % b
GCD = a # 최대공약수
return A * B // greatest
# arr에서 앞 2개씩 접근하면서 최소공배수 갱신
def solution(arr):
arr.sort()
temp = arr[0]
for i in range(0, len(arr)-1):
temp = least(temp, arr[i+1])
return temp수가 여러 개 주어졌고, 이들을 포괄할 수 있는 최소공배수를 구해야 한다. 그러기 위해선 2개 수의 최소공배수를 구하는 함수를 유클리드 알고리즘(유클리드 호제법)을 통해 구현하고, arr의 앞에서부터 수 2개씩 접근하면서 이들을 모두 포괄할 수 있도록 최소공배수를 갱신해 나간다.
유클리드 알고리즘
유클리드 호제법 ( = 유클리드 알고리즘)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 뜻한다.
2개의 자연수 a, b (a > b)에 대해서 a를 b로 나눈 나머지 ( = a % b)를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이 설명에 따라 위 예시를 다시 살펴보면 아래와 같이 중간 과정을 확인할 수 있다.
참고로 유클리드 알고리즘을 구현한 math 라이브러리가 있는데 이를 이용해서 최대공약수를 간단히 구한 후 최소공배수를 구하는 함수를 구현할 수 있다. 코드는 아래과 같다.
import math
def LCM(a, b):
return a * b / math.gcd(a, b)