파이썬으로 LCM이 K 이하인 가장 긴 부분 수열 찾기

서로 다른 n개의 숫자로 이루어진 배열 A와 양의 정수 K가 주어졌을 때, 최소공배수(LCM)가 K 이하가 되는 가장 긴 부분 수열(sub-sequence)을 찾는 문제를 살펴보겠습니다.

조건을 만족하는 부분 수열을 찾았다면 그 LCM 값, 부분 수열의 길이, 그리고 구성 요소들의 인덱스(0부터 시작)를 반환해야 하며, 만족하는 부분 수열이 존재하지 않으면 -1을 반환합니다.

예를 들어 입력이 A = [3, 4, 5, 6], K = 20이라고 해봅시다. 이때 출력은 다음과 같습니다.

LCM = 12
Length = 3
Indexes = [0, 1, 3]

인덱스 0, 1, 3에 해당하는 값은 각각 3, 4, 6이며, 이 세 수의 최소공배수는 12로 K인 20 이하입니다. 참고로 값 5를 포함하면 LCM이 60이 되어 조건을 벗어나므로 제외됩니다.

해결 알고리즘

이 문제의 핵심 아이디어는 카운팅(counting) 기법입니다. 1부터 K까지의 각 숫자에 대해 '배열 A의 원소 몇 개가 이 숫자를 나누어떨어지게 하는지'를 미리 계산해 두면, 어떤 값이 LCM이 될 때 가장 많은 원소를 포함할 수 있는지 한 번의 스캔으로 알 수 있습니다.

구체적인 단계는 다음과 같습니다.

n := 배열 A의 크기
my_dict := 각 숫자의 등장 횟수를 저장하는 딕셔너리(맵)
i를 0부터 n-1까지 반복하며 my_dict[A[i]] 값을 1씩 증가시킵니다.
count := 크기가 (K+1)이고 0으로 초기화된 배열
my_dict의 각 키(key)에 대해:
- key ≤ K라면, i := 1부터 시작하여 key * i ≤ K인 동안 count[key * i]에 my_dict[key]만큼 더합니다. (즉, key의 모든 배수 위치에 key를 나누는 원소 개수를 누적)
- key > K라면 반복문을 종료합니다. K보다 큰 값은 어떤 LCM의 약수가 될 수 없습니다.
lcm := 0, size := 0으로 초기화합니다.
i를 1부터 K까지 반복하며, count[i] > size이면 size := count[i], lcm := i로 갱신합니다.
lcm이 여전히 0이라면 조건을 만족하는 부분 수열이 없으므로 -1을 반환합니다.
그렇지 않으면 lcm과 size를 출력하고, lcm % A[i] == 0을 만족하는 모든 인덱스 i를 출력합니다.

예제 코드

아래는 위 알고리즘을 파이썬으로 구현한 코드입니다.

from collections import defaultdict

def get_seq(A, k):
    n = len(A)
    my_dict = defaultdict(lambda: 0)
    for i in range(0, n):
        my_dict[A[i]] += 1

    count = [0] * (k + 1)
    for key in my_dict:
        if key <= k:
            i = 1
            while key * i <= k:
                count[key * i] += my_dict[key]
                i += 1
        else:
            break

    lcm = 0
    size = 0
    for i in range(1, k + 1):
        if count[i] > size:
            size = count[i]
            lcm = i

    if lcm == 0:
        print(-1)
    else:
        print("LCM = {0}, Length = {1}".format(lcm, size))
        print("Index values: ", end="")
        for i in range(0, n):
            if lcm % A[i] == 0:
                print(i, end=" ")

k = 20
A = [3, 4, 5, 6]
get_seq(A, k)

입력

[3, 4, 5, 6], 20

출력

LCM = 12, Length = 3
Index values: 0 1 3

동작 원리와 시간 복잡도

이 알고리즘이 왜 동작하는지 살펴보겠습니다. 어떤 값 m이 부분 수열의 LCM이 되려면, 포함되는 모든 원소가 m의 약수여야 합니다. 따라서 count[m]에는 'm을 나누어떨어지게 하는 배열 원소의 개수'가 저장됩니다.

각 고유한 값 key에 대해 K 이하의 배수들을 순회하면서 카운트를 누적하기 때문에, 전체 시간 복잡도는 조화급수의 합에 해당하는 O(n + K log K) 수준입니다. 이는 모든 가능한 LCM 후보를 완전탐색하는 것보다 훨씬 효율적입니다.

마지막 단계에서 최대 카운트를 가진 값을 LCM으로 선택한 뒤, 해당 LCM으로 나누어떨어지는 모든 원소의 인덱스를 출력하면 원하는 답을 얻을 수 있습니다.