파이썬으로 리스트의 최대공약수(GCD) 구하기

문제 개요

양의 정수로 이루어진 리스트 nums가 주어졌을 때, 리스트의 모든 숫자를 나눌 수 있는 가장 큰 양의 정수, 즉 최대공약수(GCD)를 구하는 문제입니다.

예를 들어 입력이 [14, 28, 70, 56]이라면, 이 네 숫자를 모두 나눌 수 있는 가장 큰 수는 14이므로 출력 결과는 14가 됩니다.

해결 접근 방법

최대공약수에는 다음과 같은 중요한 성질이 있습니다.

gcd(a, b, c) = gcd(gcd(a, b), c)

즉, 두 수씩 차례대로 최대공약수를 구하다 보면 전체 리스트의 최대공약수를 얻을 수 있습니다. 이 성질을 활용한 알고리즘은 다음과 같습니다.

• 변수 ans를 리스트의 첫 번째 요소로 초기화합니다.
• 리스트의 각 요소 x에 대해 ans와 x의 최대공약수를 구하여 ans에 저장합니다.
• 모든 요소를 처리한 후 ans를 반환합니다.

구현 예제

파이썬에서는 math 모듈의 gcd() 함수를 사용하면 간단하게 구현할 수 있습니다.

import math

class Solution:
    def solve(self, nums):
        ans = nums[0]
        for x in nums:
            ans = math.gcd(ans, x)
        return ans

ob = Solution()
print(ob.solve([14, 28, 70, 56]))

입력

[14, 28, 70, 56]

출력

14

더 간결한 방법들

파이썬 3.9부터는 math.gcd() 함수에 여러 개의 인자를 동시에 전달할 수 있어 코드를 더욱 짧게 작성할 수 있습니다.

import math

def solve(nums):
    return math.gcd(*nums)

또한 functools.reduce를 활용하면 누적 방식으로 우아하게 표현할 수도 있습니다.

from functools import reduce
import math

def solve(nums):
    return reduce(math.gcd, nums)

시간 복잡도

리스트의 길이를 n이라고 할 때, 각 요소마다 한 번씩 gcd 연산을 수행하므로 전체 시간 복잡도는 O(n log M)입니다(여기서 M은 리스트 내 최댓값). 유클리드 호제법 기반의 math.gcd는 매우 효율적으로 동작하므로 실무에서도 널리 사용됩니다.