알고리즘 문제를 풀다가 한참을 고민해도 문제가 풀리지 않아 풀이를 찾아보다가 찾은 GCD와 LCM입니다. GCD와 LCM이 무엇인지와 로직을 설명해보겠습니다.

⚗️ GCD

GCD는 Greatest Common Divisor을 말합니다. 한국어로는 최대공약수이죠. 반복문으로 최대공약수를 찾는 로직을 만들 수 있겠지만 조금 다른 방법을 사용합니다. 유클리드 호제법을 사용해서 풀어보겠습니다.

유클리드 호제법
1. 최대공약수를 구하는 함수 gcd(x,y)가 있습니다.
2. x % y == 0이면 gcd(x,y) = y 입니다.
3. x % y != 0이면 gcd(x,y) = g(y,x%y)를 해줍니다.
4. 2번이 만족할 때까지 2,3 단계를 반복합니다.

위와 같은 방법을 Python 코드로 짠다면 아래와 같습니다.

def gcd(x, y):
	while y:
   		x,y = y,x%y
	return x

🔮 LCM

LCM은 Leastest Common Multiple를 말합니다. 최대공약수를 배웠으면 이번에는 최소공배수를 배우겠습니다. LCM은 GCD를 사용하는 함수로 만들어집니다. 두 수 x,y의 곱한 값에 최대공약수를 나눠주면 최소공배수를 구할 수 있습니다.

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

위와 같은 방법으로 손쉽게 최소공배수를 구할 수 있습니다.

여러 수의 최소공배수

만약 여러수의 최소 공배수를 구해야하면 어떻게 해야할까요?

위의 LCM을 그대로 사용하면 됩니다. 여러 개의 수가 주어진다면 맨앞부터 차례대로 대입하면 됩니다.

# arr = [2,6,8,14]

def solution(arr):
	for i in range(len(arr)-1):
   		arr[i+1] = lcm(a[i],a[i+1])
   	
   	return arr[-1]