[프로그래머스] N개의 최소공배수 python / 최대공약수, 최소공배수, 유클리드 호제법

나이가 드니,.. 최소 공배수가 뭐더라 최대공약수가 뭐더라,....

암튼 해당 알고리즘이 바로바로 생각날 수 있도록 문제를 기록한다 !

 

최대공약수(Greatest Common Divisor, GCD)

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

두개의 자연수를 1~N까지 나누어 공통되는 것을 찾아 그 중 max 값을 구하면 구할 순 있겠지만 ! 높은 시간 복잡도를 가진다.

이에 최대공약수를 간단하게 풀 수 있는 유클리드 호제법을 사용한다.

유클리드 호제법: 
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

그러나 ! python에서 제공하는 math 함수를 쓰면 됨

import math
math.gcd(a, b)

 

최소공배수 (Least Common Multiple, LCM)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

최소공배수는 다음과 같이 구할 수 있다.

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

코드로 구현하면 다음과 같다.

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

 

 

 

그럼 문제로 돌아가서, N개의 수가 주어졌을 때는..?

> for loop를 돌면 된다. 

문제

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

CODE

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