0. 문제
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
1. 나의 풀이
import math
def lcm(a, b):
return abs(a * b) // math.gcd(a, b)
def solution(arr):
answer = arr[0]
i = 1
for i in range(len(arr)):
answer = lcm(answer, arr[i])
return answer2. gcd, lcm
1) GCD(Great Common Divisor): 최대공약수, 유클리드 알고리즘
- 두 수나 여러 수의 공통된 약수 중에서 가장 큰 수
def gcd(a, b):
while b:
a, b = b, a % b
return a예를 들어 56과 98의 최대공약수를 구한다면
56 % 98 = 42
56과 42의 최대공약수를 구하는 것이된다. 이를 반복족으로 하는 것이 유클리드 알고리즘
왜냐? a와 b의 선형조합(ax + by로 표현되는 수의 집합)
a와 b의 최대공약수를 d라고 할 때 선형 조합으로 표현. 베주의 항등식에서 알 수 있다.
q 는 몫
r 이 나머지
a = bq + r
r = a - bq
따라서, r도 a와 b의 선형조합, 그렇기 대문에 a와 b의 최대공약수 d는 b와 r의 최대공약수와 동일해야 한다. 그래서 나머지 연산을 통해 GCD를 계속 찾아나가는 것베주의 항등식이란?
정수 a와 b에 대해, 만약 d가 a와 b의 최대공약수(GCD)라면, 정수 x와 y가 존재하여 다음 식이 성립한다는 것
ax + by = d
이 때 x와 y가 존재하여 만족된다.
2) lcm(Least Commom Multiple)
- a와 b는 각각 GCD(a, b)로 나누어 떨어짐
a = GCD(a,b) X m
b = GCD(a,b) X n
m과 n은 서로소(공약수가 1뿐인 두수), 서로소가 아니라면 최대공약수가 아니다.
그래서
LCM(a,b) = GCD(a,b) X m X n
여기서
m = a/GCD(a,b)
n = b/GCD(a,b)
그러므로 LCM = GCD(a,b) X a/GCD(a,b) X b/GCD(a,b)
= a X b / GCD(a,b)
