파이썬으로 두 개 이상의 숫자(배열)의 최대공약수(GCD) 구하는 프로그램

이 글에서는 아래와 같은 문제 상황에 대한 해결 방법을 살펴보겠습니다.

문제 정의

문제: 숫자로 이루어진 배열이 주어졌을 때, 해당 배열에 포함된 모든 숫자의 최대공약수(GCD, Greatest Common Divisor)를 구해야 합니다.

두 개 이상의 숫자에 대한 최대공약수는 인자로 주어진 모든 숫자에 공통으로 나타나는 소인수들의 곱과 같습니다. 또 다른 방법으로는, 인자들을 두 개씩 짝지어 반복적으로 GCD를 계산하는 방식도 있습니다.

여기서는 후자의 방법, 즉 유클리드 호제법(Euclidean Algorithm)을 활용해 두 수씩 묶어가며 GCD를 누적 계산하는 방식을 구현해 보겠습니다.

구현 원리

핵심 아이디어는 간단합니다.

1. 먼저 배열의 첫 번째 요소와 두 번째 요소의 GCD를 구합니다.
2. 그 결과값과 세 번째 요소의 GCD를 다시 구합니다.
3. 이 과정을 배열의 마지막 요소까지 반복하면, 그 최종 결과가 전체 배열의 GCD가 됩니다.

이것이 성립하는 이유는 gcd(a, b, c) = gcd(gcd(a, b), c)라는 수학적 성질 때문입니다.

예제 코드

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

위 코드에서 사용된 변수와 함수는 모두 아래 이미지와 같이 전역 범위(global scope)에 선언되어 있습니다.

코드 설명

findgcd 함수는 유클리드 호제법을 구현한 것으로, y가 0이 될 때까지 x와 y를 갱신하며 나머지 연산을 반복합니다. 루프가 종료되면 x에 마지막 남은 값, 즉 최대공약수가 저장됩니다.

메인 로직에서는 리스트의 첫 두 요소로 초기 GCD를 구한 뒤, for 루프를 통해 나머지 요소들과 차례대로 GCD를 계산하여 최종 결과를 도출합니다.

결론

이 글에서는 파이썬을 이용해 주어진 숫자 배열의 최대공약수를 구하는 방법을 배웠습니다. 유클리드 호제법을 기반으로 두 수씩 짝지어 GCD를 반복 계산하는 이 접근 방식은 코드가 간결할 뿐만 아니라, 임의의 길이를 가진 배열에도 손쉽게 확장할 수 있다는 장점이 있습니다.