[Python] 최대공약수, 최소공배수, N개의 최소공배수

최대공약수 (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의 최대공약수를 유클리드 호제법을 활용해 계산하면 다음과 같습니다.

1. 1071은 1029로 딱 나눠지지 않기 때문에 1071을 1029로 나눈 나머지를 구함 -> 42
2. 1029는 42로 딱 나눠지지 않기 때문에 1029를 42로 나눈 나머지를 구함 -> 21
3. 42는 21로 나눠짐
4. 최대공약수는 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

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

N개의 최소공배수

최소공배수는 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