Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 배열의 최소 원소를 제거해 GCD를 키우는 알고리즘

N개의 숫자로 이루어진 배열이 주어졌을 때, 남은 숫자들의 최대공약수(GCD)가 처음 전체 배열의 GCD보다 커지도록 제거해야 하는 원소의 최소 개수를 구하는 문제를 살펴보겠습니다.

문제 이해하기

예를 들어 입력이 [6, 9, 15, 30]이라고 가정해 봅시다. 네 숫자의 초기 GCD는 3입니다. 여기서 6과 9를 제거하면 남은 숫자는 15와 30이 되고, 이때의 GCD는 15가 됩니다. 15 > 3이므로 필요한 최소 제거 횟수는 2입니다.

접근 방법

핵심 아이디어는 다음과 같습니다.

  • 전체 배열의 GCD를 g라고 할 때, 각 원소를 g로 나누면 모든 원소의 공통 약수가 사라집니다.
  • 이 상태에서 특정 소수 p가 k개의 원소에 공통적으로 포함되어 있다면, 그 소수들을 모두 지키기 위해 제거해야 하는 원소는 (n − k)개입니다.
  • 따라서 각 소수별 등장 횟수를 세고, (n − 등장 횟수)의 최솟값을 찾으면 됩니다.

효율적인 소인수분해를 위해 에라토스테네스의 체를 변형하여 각 숫자의 가장 작은 소인수(SPF, Smallest Prime Factor)를 미리 계산해 둡니다.

알고리즘 단계

  1. INF := 100001로 설정하고, spf를 0부터 INF까지의 값으로 초기화합니다.
  2. sieve() 함수를 정의합니다.
    • i를 4부터 INF까지 2씩 증가시키며 spf[i] := 2로 설정합니다.
    • i를 3부터 INF까지 증가시키며, i² > INF이면 종료합니다.
    • spf[i] == i인 경우(즉, i가 소수인 경우), j를 2*i부터 INF까지 i씩 증가시키며 spf[j] == j일 때 spf[j] := i로 갱신합니다.
  3. calc_fact(x) 함수를 정의합니다.
    • x가 1이 아닌 동안 ret 리스트에 spf[x]를 추가하고, x := x // spf[x](정수 나눗셈)로 갱신합니다.
    • 완료된 ret(소인수 목록)을 반환합니다.
  4. 메인 로직:
    • g := 0으로 두고, 모든 원소에 대해 g := gcd(a[i], g)를 반복해 전체 GCD를 구합니다.
    • 각 원소를 g로 나누어 갱신합니다.
    • 각 원소를 calc_fact()로 소인수분해한 뒤, 중복 없는 소수 집합 s를 만들고 my_map에 각 소수의 등장 횟수를 누적합니다.
    • minimum := 10⁹로 초기화한 후, my_map의 각 항목에 대해 (n − 등장 횟수)가 minimum보다 작으면 갱신합니다.
    • minimum이 10⁹가 아니면 minimum을, 그렇지 않으면 -1을 반환합니다(-1은 어떤 제거로도 GCD를 키울 수 없음을 의미).

구현 예제

아래 파이썬 코드로 위 과정을 직접 확인해 보세요.

from math import gcd as __gcd
INF = 100001
spf = [i for i in range(INF)]
def sieve():
   for i in range(4, INF, 2):
      spf[i] = 2
   for i in range(3, INF):
      if i**2 > INF:
         break
      if (spf[i] == i):
         for j in range(2 * i, INF, i):
            if (spf[j] == j):
               spf[j] = i
def calc_fact(x):
   ret = []
   while (x != 1):
      ret.append(spf[x])
      x = x // spf[x]
   return ret
def minRemove(a, n):
   g = 0
   for i in range(n):
      g = __gcd(a[i], g)
   my_map = dict()
   for i in range(n):
      a[i] = a[i] // g
   for i in range(n):
      p = calc_fact(a[i])
      s = dict()
      for j in range(len(p)):
         s[p[j]] = 1
      for i in s:
         my_map[i] = my_map.get(i, 0) + 1
   minimum = 10**9
   for i in my_map:
      first = i
      second = my_map[i]
      if ((n - second) <= minimum):
         minimum = n - second
   if (minimum != 10**9):
      return minimum
   else:
      return -1
a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))

입력

[6, 9, 15, 30], 4

출력

2

정리

이 알고리즘은 에라토스테네스의 체를 활용한 선형 시간의 소인수 준비 덕분에 각 원소의 소인수분해를 빠르게 처리할 수 있습니다. 시간 복잡도는 대략 O(N·log(max(a)) + INF)이며, 배열이 클 때도 효율적으로 동작합니다. 만약 어떤 소수도 둘 이상의 원소에 공통으로 나타나지 않는다면 -1이 반환되어, 제거만으로는 GCD를 키울 수 없다는 것을 알려줍니다.