[level 2] N개의 최소공배수(최소공배수, 최대공약수 복습)

문제

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

 

문제 풀이 접근법1

1) 처음 두 개의 수의 최소 공배수를 구한다.

2) 2부터 len(arr)까지 for문을 돌며 arr의 i번째 원소와 1)에서 구한 최소 공배수의 공배수를 구하며 최소 공배수를 업데이트 한다. 

import math
def solution(arr):
    
    lcm = int((arr[0] * arr[1]) / math.gcd(arr[0], arr[1])) 

    for i in range(2, len(arr)):
        lcm = int((arr[i] * lcm) / math.gcd(arr[i], lcm))
        
    return lcm

 

 

---

최대공약수 복습 

유클리드 호제법(in 파이썬)

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

 

 

최소공배수 복습

lcm(최소공배수) =  ( a * b ) / gcd(a, b)

즉, 두 수의 최소공배수는 두 수를 곱한 수에 두 수의 최대공약수를 나눈 것과 같다. 

def lcm(a, b):

	origin = a * b

	while b < 0:
    	 a, b = b, a% b
         
	return origin / a