이번 글에서는 아래 문제 상황에 대한 해결 방법을 알아보겠습니다.
문제 정의
숫자로 이루어진 배열이 주어졌을 때, 배열에 포함된 모든 숫자의 최대공약수(GCD, Greatest Common Divisor)를 구해야 합니다.
두 개 이상의 숫자에 대한 최대공약수는 인자로 주어진 모든 숫자에 공통으로 등장하는 소인수들의 곱과 같습니다. 또한, 두 수씩 짝지어 GCD를 반복적으로 계산하는 방식으로도 구할 수 있습니다. 즉, gcd(a, b, c) = gcd(gcd(a, b), c)라는 성질을 이용하는 것입니다.
여기서는 후자의 방법, 즉 유클리드 호제법(Euclidean algorithm)을 활용해 두 수의 GCD를 구한 뒤, 그 결과를 배열의 다음 숫자와 계속 계산해 나가는 방식을 구현해 보겠습니다.
유클리드 호제법의 원리
유클리드 호제법은 두 수 a와 b(a > b)의 최대공약수가 'a를 b로 나눈 나머지'와 'b'의 최대공약수와 같다는 원리를 이용합니다. 나머지가 0이 될 때까지 이 과정을 반복하면, 마지막에 남는 값이 곧 두 수의 최대공약수가 됩니다.
구현 예제
def findgcd(x, y):
while(y):
x, y = y, x % y
return x
l = [22, 44, 66, 88, 99]
num1 = l[0]
num2 = l[1]
gcd = findgcd(num1, num2)
for i in range(2, len(l)):
gcd = findgcd(gcd, l[i])
print("Gcd is: ", gcd)실행 결과
Gcd is: 11
동작 과정 살펴보기
위 코드가 실행되는 과정을 단계별로 확인해 보면 다음과 같습니다.
- 22와 44의 GCD → 22
- 22와 66의 GCD → 22
- 22와 88의 GCD → 22
- 22와 99의 GCD → 11
배열의 모든 요소에 공통된 약수 중 가장 큰 값은 11이므로, 최종 결과로 11이 출력됩니다.
참고: math 모듈 활용하기
Python 3.5 이상에서는 표준 라이브러리의 math.gcd() 함수를 사용할 수 있으며, functools.reduce와 조합하면 배열 전체의 GCD를 간결하게 구할 수도 있습니다.
from math import gcd from functools import reduce l = [22, 44, 66, 88, 99] print(reduce(gcd, l)) # 출력: 11
결론
이번 글에서는 유클리드 호제법을 활용해 배열로 주어진 여러 숫자의 최대공약수를 효율적으로 구하는 방법을 알아보았습니다. 두 수의 GCD를 반복적으로 적용하는 이 접근 방식은 구현이 간단하면서도 시간 복잡도 측면에서도 효율적이므로, 실무에서 유용하게 활용할 수 있습니다.