N개의 최소공배수 파이썬 - ngaeui choesogongbaesu paisseon

Question

문제: https://programmers.co.kr/learn/courses/30/lessons/12953

목차 Show

< 프로그래머스 - N개의 최소공배수 (LV2) >
최대공약수 (Greatest Common Divisor)
최소공배수 (Least Common Multiple)

코딩테스트 연습 - N개의 최소공배수

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배

programmers.co.kr

문제 설명

문제 설명

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

제한 사항

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

입출력 예

arrresult

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

정답

import math


def solution(arr):
    answer = 1
    for n in arr:
        answer = n * answer // math.gcd(answer, n)
    return answer

풀이

파이썬의 내장 함수인 math.lcm()을 이용하여 최소 공배수를 구할 수 있습니다. 그러나 프로그래머스에서는 해당 함수를 지원하지 않기 때문에 다른 공식을 이용하여 문제를 풀어야 합니다.

A와 B의 최소공배수 = A * B / A와 B의 최대공약수

파이썬에서는 math.gcd()를 이용하여 최대공약수를 빠르게 구할 수 있기 때문에 위의 공식을 이용하여 문제를 풀면 됩니다.

Programmers/Python

by Sin_ 2021. 12. 6.

안녕하세요 뚜디 입니다

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - N개의 최소공배수

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배

programmers.co.kr

< 프로그래머스 - N개의 최소공배수 (LV2) >

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

1. 연습 문제

※ 문제 설명

두 수의 최소공배수(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

2. 문제 풀이

임의의 리스트에 입력된 임의의 숫자들의 최소공배수를 찾는 문제입니다.
1. 임의의 리스트에서 가장 큰 숫자를 찾는다->리스트 마지막 인자값
2. 가장 큰 숫자와 임의의 리스트에 인자값들이 나누어 떨어지는지 확인한다.
: 모든 인자값들이 나누어 떨어진다면 최소공배수
3. 나누어 떨어지지 않는경우 가장 큰 숫자+1 을하여 2번동작을 무한반복한다.

3. 소스 코드

def solution(arr):
    answer = 0
    count = 0
    temp = arr[-1]

    while count != len(arr):
        for j in range(len(arr)):
            if (temp % arr[j] == 0):
                count += 1
            else:
                count = 0
                temp += 1
                break 
        

    answer = temp
    return answer

임의의 리스트에서 가장 큰 값을 가장 마지막 인자값이라고 단정지었는데, 문제에서 그 어떤 언급도 없었다
arr[-1]보단 MAX(arr)이 더 맞는 접근이였을거 같다.

4. 결과

댓글0

최대공약수 (Greatest Common Divisor)

최대공약수는 주어진 두 수 x, y에서 x의 약수이면서 y의 약수인 수 중 최대값을 의미합니다. 최대공약수를 구하는 간단한 방법은 1에서 x와 y 중 작은 값의 범위에서 공약수(둘 모두 나머지가 0)를 모두 구한 다음 이 수들 중 최대값을 구하는 방법입니다. 1부터 x 또는 y 중 작은 값까지 반복하며 값을 구할 수 있지만 유클리드 호제법(Euclidean algorithm)을 이용하면 간단하게 계산이 됩니다.

유클리드 호제법의 공식은 다음과 같습니다.

최대공약수를 구하는 함수를 gcd(x,y)라고 가정
x % y = 0이라면 gcd(x, y) = y가 성립
x % y != 0이라면 gcd(x, y) = gcd(x, x % y)가 성립
2번이 될 때까지 2~3번을 반복

예를 들어, 1071과 1029의 최대공약수를 유클리드 호제법을 활용해 계산하면 다음과 같습니다.

1071은 1029로 딱 나눠지지 않기 때문에 1071을 1029로 나눈 나머지를 구함 -> 42
1029는 42로 딱 나눠지지 않기 때문에 1029를 42로 나눈 나머지를 구함 -> 21
42는 21로 나눠짐
최대공약수는 21

이를 파이썬 코드로 짜면 아래와 같습니다.

def gcd(x, y):
   # y가 0이 될 때까지 반복
   while y:
       # y를 x에 대입
       # x를 y로 나눈 나머지를 y에 대입
       x, y = y, x % y
   return x


print(gcd(1071, 1029))


# 21

파이썬에서는 이를 구현할 필요없이 내장함수 math 모듈에서 기능을 제공해주고 있습니다.

from math import gcd




print(gcd(1071, 1029))


# 21

fractions 모듈의 math는 삭제예정이니 math 모듈을 사용하는 것이 좋습니다.

최소공배수 (Least Common Multiple)

최소공배수는 x와 y의 공통된 배수 가운데 최소값을 의미합니다. 더 쉽게 말해서, 최소공배수는 주어진 수인 x,y의 곱에서 x,y의 최대공약수를 나누어 준 것과 같습니다. 즉, 유클리드 호제법을 사용해 최대공약수를 구한 다음, x와 y의 곱한 값을 나눠주면 최소공배수를 구할 수 있습니다.

아래는 파이썬에서 제공해주는 내장함수 gcd를 사용해 최소공배수를 구한 예제입니다.

from math import gcd

def lcm(x, y):
   return x * y // gcd(x,y)

print(lcm(1071, 1029))


# 52479

파이썬에서 // 연산자는 나눈 값의 몫을 반환합니다.

최소공배수는 2개의 수를 대상으로 실행하기 때문에 주어진 수가 3개 이상일 때, 막막해 보이지만 해결방법은 간단합니다. 먼저 2개의 수에 대해 최소공배수를 구한 다음, 그 값과 계산하지 않은 값들 중 1개를 선택해 다시 최소공배수를 구합니다. 이렇게 모든 수에 대해 최소공배수를 구하면 N개의 최소공배수를 구할 수 있습니다.

아래는 파이썬 코드입니다.

from math import gcd


def solution(arr):
    def lcm(x, y):
        return x * y // gcd(x, y)

    while True:
        arr.append(lcm(arr.pop(), arr.pop()))
        if len(arr) == 1:
            return arr[0]


print(solution([2, 6, 8, 14]))

# 168

Python lcm gcd 파이썬 공배수 Python 최소 공배수 파이썬 gcd 리스트 N-Queen 파이썬