Python으로 모든 쌍의 gcd() 결과에서 원래 숫자 복원하기

문제 개요

어떤 배열의 모든 가능한 요소 쌍에 대한 최대공약수(GCD) 값들이 주어진 배열 A가 있다고 가정해 봅시다. 이때 우리의 목표는 이 GCD 배열을 만드는 데 사용된 원래 숫자들을 찾아내는 것입니다.

예를 들어, 입력이 A = [6, 1, 1, 13]이라면 출력은 [13, 6]이 됩니다. 그 이유는 다음과 같습니다.

gcd(13, 13) = 13
gcd(13, 6) = 1
gcd(6, 13) = 1
gcd(6, 6) = 6

즉, 두 숫자 13과 6으로 만들 수 있는 네 가지 쌍의 GCD 결과가 정확히 입력 배열과 일치합니다.

해결 접근 방식

이 문제는 다음 단계를 통해 해결할 수 있습니다.

n := 배열 A의 크기
배열 A를 내림차순으로 정렬합니다.
occurrence := A[0] 크기만큼의 배열을 생성하고 0으로 초기화합니다.
i를 0부터 n까지 반복하면서 occurrence[A[i]] 값을 1씩 증가시켜 각 숫자의 등장 횟수를 기록합니다.
size := n의 제곱근의 정수 부분 (원래 배열의 실제 길이)
res := A와 같은 크기의 배열을 생성하고 0으로 초기화합니다.
l := 0 (결과 배열의 현재 인덱스)
i를 0부터 n까지 반복하며 다음을 수행합니다.
- occurrence[A[i]] > 0인 경우:
  - res[l] := A[i]
  - occurrence[res[l]] -= 1
  - l += 1
  - j를 0부터 l까지 반복하며 i와 j가 다를 때:
    - g := gcd(A[i], res[j])
    - occurrence[g] -= 2 (쌍은 대칭이므로 2씩 감소)
res의 인덱스 0부터 size까지 반환합니다.

핵심 아이디어는 가장 큰 수부터 처리하는 것입니다. 내림차순으로 정렬하면 가장 큰 수가 항상 원래 배열의 요소이며(자기 자신과의 GCD가 자기 자신이므로), 이후 작은 수들은 이미 확정된 숫자들과의 GCD 관계를 검증하면서 선택 여부를 결정하게 됩니다.

구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

from math import sqrt, gcd

def get_actual_array(A):
    n = len(A)
    A.sort(reverse=True)
    occurrence = [0 for i in range(A[0] + 1)]
    for i in range(n):
        occurrence[A[i]] += 1
    size = int(sqrt(n))
    res = [0 for i in range(len(A))]
    l = 0
    for i in range(n):
        if (occurrence[A[i]] > 0):
            res[l] = A[i]
            occurrence[res[l]] -= 1
            l += 1
            for j in range(l):
                if (i != j):
                    g = gcd(A[i], res[j])
                    occurrence[g] -= 2
    return res[:size]

A = [6, 1, 1, 13]
print(get_actual_array(A))

입력

[6, 1, 1, 13]

출력

[13, 6]

동작 원리 설명

입력 [6, 1, 1, 13]을 내림차순으로 정렬하면 [13, 6, 1, 1]이 됩니다. 먼저 13이 선택되고, 그다음 6이 선택됩니다. 이 시점에서 gcd(13, 6) = 1에 해당하는 occurrence 값이 감소합니다. 남은 두 개의 1은 이미 사용된 쌍들의 GCD 결과로 소진되므로 최종 결과에는 포함되지 않습니다. 마지막으로 size = √4 = 2이므로 처음 두 개의 요소 [13, 6]이 반환됩니다.

이 알고리즘의 시간 복잡도는 O(n²)이며, 여기서 n은 입력 배열의 길이입니다. 각 후보 숫자에 대해 기존 결과 배열의 모든 요소와 GCD를 계산해야 하기 때문입니다.