문제 설명
양수로만 이루어진 배열 nums가 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 nums의 모든 비어 있지 않은 부분 수열(subsequence)에서 만들어질 수 있는 서로 다른 GCD(최대공약수)의 개수입니다.
여기서 수열의 GCD란, 해당 수열의 모든 숫자를 나머지 없이 나누어 떨어지게 하는 가장 큰 값을 의미합니다.
입력 예시
nums = [4, 6, 18]
출력 결과
4
그 이유는 다음과 같습니다.
- gcd([4]) = 4
- gcd([6]) = 6
- gcd([18]) = 18
- gcd([4, 6]) = 2
- gcd([4, 18]) = 2
- gcd([6, 18]) = 6
- gcd([4, 6, 18]) = 2
따라서 등장하는 GCD 값은 {2, 4, 6, 18}로 총 4가지입니다.
풀이 접근 방법
모든 부분 수열을 하나씩 생성해 GCD를 계산하면 지수 시간이 걸려 매우 비효율적입니다. 대신 에라토스테네스의 체와 유사한 아이디어를 활용할 수 있습니다. 각 후보 값 x에 대해 x의 배수들만 순회하면서 실제 배열에 존재하는 값들의 GCD를 누적 계산하고, 그 결과가 x와 일치하는지 확인하는 방식입니다.
구체적인 단계는 다음과 같습니다.
- T := nums의 최댓값 + 1
- nums := 중복을 제거한 집합(set)으로 변환
- ans := 0
- x를 1부터 T-1까지 반복
- g := 0
- y를 x부터 T-1까지 x씩 증가시키며 반복
- y가 nums에 존재하면 g := gcd(g, y)
- g == x이면 내부 반복 종료
- g == x이면 ans를 1 증가
- ans 반환
Python 구현 예제
다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
from math import gcd
def solve(nums):
T = max(nums) + 1
nums = set(nums)
ans = 0
for x in range(1, T):
g = 0
for y in range(x, T, x):
if y in nums:
g = gcd(g, y)
if g == x:
break
if g == x:
ans += 1
return ans
nums = [4, 6, 18]
print(solve(nums))
입력
[4,6,18]
출력
4
복잡도 분석
이 알고리즘의 시간 복잡도는 조화급수 형태로 O(M log M)입니다. 여기서 M은 배열의 최댓값입니다. 각 x에 대해 x의 배수 개수만큼만 순회하므로 전체 연산 횟수는 M/1 + M/2 + ... + M/M ≈ M·log M이 되며, 모든 부분 수열을 탐색하는 완전 탐색 방식에 비해 훨씬 효율적입니다.