⭐N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

핵심 아이디어

최대공약수(GCD)

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. 최대 공약수를 간단하게 풀 수 있는 유클리드 호제법을 사용한다.

유클리드 호제법이란 2개의 자연수 a,b(a>b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

def gcd(a,b):
    while b:
        r = a % b
        a,b = b,r
    return a

파이썬에서는 math 라이브러리를 활용해서 풀 수 있다.

import math
math.gcd(a, b)

최대공배수(LCM)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 최소 공배수는 다음과 같이 구할 수 있다.

 

최소 공배수 = 두 자연수의 곱 / 최대 공약수

import math
def lcm(a, b):
    return a * b // math.gcd(a,b)

코드 구현

import math
def lcm(a,b):
    return a*b // math.gcd(a,b)

def solution(arr):
    n = arr[0] # 처음에는 첫번째 원소를 최소공배수로 초기화
    for i in arr[1:]:
        n = lcm(n,i)
    return n