NIRVANA
[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
'Coding test(Python3) > Programmers' 카테고리의 다른 글
[level 2] 귤 고르기 (0) | 2023.11.13 |
---|---|
[level 2] 멀리 뛰기 (1) | 2023.11.12 |
[level 2]예상 대진표 (0) | 2023.11.07 |
[level 2] 구명보트 (파이썬 deque 복습) (1) | 2023.11.04 |
[level 2] 점프와 순간이동 (다시 풀어보기) (0) | 2023.10.02 |