python | numpy 라이브러리를 이용하여 최대공약수, 최소공배수 구하기 (gcd, lcm)

 

 

코딩테스트 문제를 해결할 때면 2개 이상의 정수의 최대공약수 또는 최소공배수를 구해야 하는 경우가 종종 있습니다. 파이썬에서 최대공약수와 최소공배수는 넘파이 라이브러리를 이용해서 아주 간단하게 구해낼 수 있는데요. 

 

먼저 함수를 소개해 드리기 전에, 최대공약수와 최소공배수를 영어로 뭐라고 부르는지 알고 넘어갈게요.

• gcd : greatest common division (최대공약수)
• lcm : lowest common multiple (최소공배수)

이런 간단한 영어 정도는 숙지해 두시면 좀더 직관적으로 쉽게 프로그래밍하실 수 있어요 :-)

 

[1] 최대공약수 구하기

import numpy as np

 

먼저 넘파이 라이브러리를 임포트해줍니다.

np.gcd(12, 20)
# 4

np.gcd(30, 45)
# 15

 

np.gcd() 함수 안에 두 정수를 넣으면 두 정수의 최대공약수를 리턴합니다. gcd인 이유는 위에서 설명한 대로 greatest common divison의 약자 gcd가 최대공약수를 의미하기 때문입니다.

 

만약 3개 이상의 정수의 최대공약수를 구하고 싶다면 어떻게 할 수 있을까요?

np.gcd.reduce([15, 25, 35])
# 5

np.gcd.reduce([15, 27, 18])
# 3

before = np.arange(0, 20, 5)
after = np.gcd.reduce(before)
after
# 5

 

np.gcd.reduce() 함수 안에 리스트 또는 넘파이 어레이를 넣어주면 리스트 또는 어레이 안의 모든 정수의 최대 공약수를 리턴합니다.

 

 

[2] 최소공배수 구하기

np.lcm(10, 14)
# 70

np.lcm.reduce([10, 15, 20])
# 60

before = np.array([3, 7, 10])
after = np.lcm.reduce(before)
after
# 210

 

np.lcm() 함수 안에 두 정수를 넣으면 두 정수의 최소공배수를 리턴합니다. lcm인 이유는 위에서 설명한 대로 lowest common multiple의 약자 lcm이 최소공배수를 의미하기 때문입니다.

 

마찬가지로 np.lcm.reduce()  함수 안에 리스트 또는 넘파이 어레이를 넣어서 3개 이상의 정수의 최소공배수도 구해낼 수 있습니다.

 

 

---

 

 

알고 있으면 아주아주 유용한 파이썬 넘파이 모듈 이용해서 최소공배수/최대공약수 구하는 방법이었습니다.

 

감사합니다 :-)