FrontEnd
Javascript
Diary
ML
CS
Django
Algorithm
AWS
Co-Work
HTML
CSS
Python
React
ReactNative

#53 알고리즘 연습 - N개의 최소공배수(Python)

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

제한 사항

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

입출력 예

arr result
[2,6,8,14] 168
[1,2,3] 6

문제풀이IDEA 이럴때는 예를 들어보는게 최고다.(수학과인데 바보다) 10과 6의 최소공배수를 구한다고 생각해보면 10은 2*5 이고 6은 2*3인데 2*5*3 이 최소공배수이다. 2*5*3 를 잘보면 10 * (6//2) 인데 이때의 2는 10과 6의 gcd 최대 공약수이다. 따라서 최대공약수와 최소공배수의 성질에 의해 연쇄적으로 두개의 숫자가 있을때 두 숫자의 곱을 할때 한 숫자에서 gcd 최대공약수만큼 나누어주면(사실 좀더 이쁘게 하면 두 숫자를 다 곱하고 최대공약수로 나눠주면 깔끔하다) 최소공배수가 나온다!

내 풀이 🏆

def solution(arr):
    answer = 1
    def gcd(n,m):
        while m:
            n , m = m, n%m
        return n

    for i in arr:
        answer *= i//gcd(answer,i)

    return answer

이문제도 푼지 1년이 다되어 가는 문제인데(포스팅을 늦게 한다 ㅠㅠ) 최근 알고리즘을 풀때 수학적 머리가 잇으면 점화식을 착착 만들어내서 좋다는 말을 들었다. 아무래도 잘하지는 못했던 수학과였지만, 조금더 논리적으로 학부에서 배우던 것을 떠올려보면 알고리즘 문제 더 나아가 여러 문제를 해결하는데 도움이 되지않을까 했던 문제였다.