알고리즘 연습 [N개의 최소공배수]
N개의 최소공배수
문제
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요. 예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.
나의 풀이
def nlcm(num):
def lcm(a, b):
mul = a * b
if a < b:
(a, b) = (b, a)
while b != 0:
(a, b) = (b, a % b)
return int(mul / a)
result = lcm(num[0], num[1])
for i in range(2, len(num)):
result = lcm(result, num[i])
return result
이미 최소공배수를 한 번 풀어논 풀이가 있어서 최소공배수 함수를 그대로 가져와서 사용했다.
다른 풀이
def nlcm(num):
# lcm = (a*b) / gcd
# gcd = (a*b) / lcm
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
result = 1
for i in range(len(num)):
result = result * num[i] / gcd(result, num[i])
return result
최대 공약수를 이용해서 푸는 방법!
최소공배수 = (a*b)/최대공약수
다른 풀이2
from functools import reduce
from fractions import gcd
def nlcm(num):
return reduce(lambda a, b : a * b / gcd(a, b), num)
reduce(lamda a,b:a+b, [1,2,3])= 6 : 함수를 순서형 자료(문자열, 리스트, 튜플)의 원소들에 누적적으로 원소에 적용