Python으로 리스트 내 모든 숫자의 최대공약수(GCD)를 구하는 프로그램

숫자들이 담긴 리스트 nums가 주어졌을 때, 이 리스트의 모든 정수를 나눌 수 있는 가장 큰 양의 정수, 즉 최대공약수(GCD)를 찾아야 합니다.

예를 들어 입력이 nums = [15, 81, 78]이라면 출력은 3이 됩니다. 3은 15, 81, 78 세 숫자를 모두 나눌 수 있는 가장 큰 정수이기 때문입니다.

해결 접근 방식

최대공약수에는 중요한 수학적 성질이 있습니다. 바로 gcd(a, b, c) = gcd(gcd(a, b), c)처럼 여러 수의 GCD를 두 수씩 묶어 순차적으로 계산할 수 있다는 점입니다. 이 성질을 이용하면 다음과 같은 알고리즘을 세울 수 있습니다.

• 리스트의 길이가 1이면, 그 자체가 답이므로 nums[0]을 그대로 반환합니다.
• div 변수에 첫 번째와 두 번째 원소의 최대공약수를 저장합니다.
• 리스트의 길이가 2라면 이 값이 곧 정답이므로 div를 반환합니다.
• 세 번째 원소부터 마지막 원소까지 차례대로 순회하면서 div와 각 원소의 최대공약수를 계산하여 div를 갱신합니다.
• 중간에 div가 1이 되면 더 이상 계산할 필요가 없으므로 즉시 1을 반환해 불필요한 연산을 줄입니다.
• 반복이 끝나면 최종 div를 반환합니다.

예제 코드

Python의 math 모듈에서 제공하는 gcd() 함수를 사용하면 손쉽게 구현할 수 있습니다.

from math import gcd

def solve(nums):
    if len(nums) == 1:
        return nums[0]

    div = gcd(nums[0], nums[1])

    if len(nums) == 2:
        return div

    for i in range(1, len(nums) - 1):
        div = gcd(div, nums[i + 1])
        if div == 1:
            return div

    return div

nums = [15, 81, 78]
print(solve(nums))

입력

[15, 81, 78]

출력

3

동작 과정 살펴보기

1. 먼저 gcd(15, 81)을 계산하면 3이 됩니다.
2. 다음으로 gcd(3, 78)을 계산하면 역시 3입니다.
3. 따라서 세 숫자의 최대공약수는 3이며, 이것이 최종 결과로 반환됩니다.

정리

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n × log(max(nums))) 수준으로 매우 효율적입니다. 특히 중간에 GCD가 1이 되면 조기에 종료하기 때문에, 서로소인 숫자가 포함된 경우 연산량을 크게 줄일 수 있다는 장점이 있습니다.