Python에서 가장 긴 증가하는 하위 시퀀스

하위 시퀀스가 무엇인지, Python에서 n-제곱 접근 방식과 이진 검색 방식을 사용하여 배열에서 가장 길게 증가하는 하위 시퀀스를 계산하는 방법을 배웁니다.

N-제곱 접근 방식을 사용하여 Python에서 가장 긴 증가하는 하위 시퀀스 계산

Python 커뮤니티 주변에서 가장 오래 증가하는 하위 시퀀스에 대한 유명한 질문이 있으며 여러 인터뷰에서 묻습니다. 이것은 Leetcode 문제이며 질문은 다음과 같습니다. 정렬되지 않은 정수 배열이 제공되고 주어진 배열의 가장 길게 증가하는 하위 시퀀스 또는 하위 집합의 길이를 찾습니다.

하위 집합은 배열의 짧은 배열과 같습니다. 각 어레이는 여러 하위 집합을 가질 수 있습니다. 다른 것은 하위 배열이 [10,9,2,5,3,7,101,18] 배열의 일부 요소이지만 연속적인 하위 시퀀스 방식이라는 것입니다.

[2, 3, 5, 7]과 같을 수 있지만 [2,3,101]일 수는 없으므로 하위 배열을 논의할 때 시퀀스를 끊을 필요가 없습니다. 그리고 하위 시퀀스에서 요소가 배열에 나타나는 순서는 동일해야 하지만 개인이 될 수 있습니다.

예를 들어, 이 경우 우리가 볼 수 있듯이 대답은 [2, 3, 7,101]입니다. 5는 없지만 하위 시퀀스이므로 괜찮습니다.

[10,9,2,5,3,7,101,18]에서 가장 길게 증가하는 하위 시퀀스를 보면 [2, 5, 7, 101]을 찾습니다. 이것은 답을 의미할 수도 있지만 답은 [2, 3, 7, 101]일 수도 있습니다. 이는 우리의 다른 하위 시퀀스이기도 합니다. [3, 7, 101]도 하위 시퀀스이지만 가장 길지 않으므로 고려하지 않습니다.

둘 이상의 조합이 있을 수 있습니다. 방금 살펴본 것처럼 길이만 반환하면 됩니다.

예제를 통해 인덱스가 0인 상태에서 시작하여 모든 다른 경로로 내려가는 재귀 솔루션을 쉽게 생각할 수 있습니다. 이 배열 [0,3,1,6,2,2,7]을 사용하여 예를 들어 0을 사용하면 3으로 이동하거나 1로 이동할 수 있습니다. 6으로 이동합니다.

그런 다음 그 시점부터 재귀적으로 계속 진행합니다. 다음 예를 보세요. 어떤 경로가 기하급수적으로 가장 길어질까요? 동적 프로그래밍 접근 방식이 있어야 한다고 쉽게 생각할 수 있습니다.

따라서 배열이 있고 각 인덱스에는 길이가 하나 이상 있습니다.

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

길이가 1인 첫 번째 색인 0에서 시작하지만 3을 사용하면 뒤를 볼 수 있으며 3이 0보다 크면 3의 길이는 2입니다. . 다시 1로 이동하면 현재 인덱스 이전의 모든 인덱스 뒤를 볼 것입니다.

제로 인덱스에서 1이 0보다 크지만 1은 3보다 크지 않으므로 이 시점에서 0과 1을 계산하고 길이를 계산합니다. 2가 됩니다.

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

6을 고려하면서 처음부터 뒤를 보면 6이 [0,1] 또는 [0,3]보다 크고 6을 포함하면 길이가 3이 됩니다. 그러면 2의 길이도 3이 되는 식으로 제곱 접근 방식입니다.

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

시간복잡도와 공간복잡도

코드로 이동하여 CalculateSubSequence라는 클래스를 생성해 보겠습니다. lengthOfLIS 함수 내에서 nums_list 변수를 1회 배열로 nums의 길이로 초기화합니다.

중첩된 루프 내에서 값이 확인 중인 숫자보다 큰지 여부를 확인합니다. 그런 다음 i의 nums_list를 가져오고 nums_list[i]를 사용하여 최대값을 가져오는 동안 nums_list 값을 업데이트합니다.

i는 외부 루프에서 반복한 후에 오고 nums_list[j]의 경우 j는 내부 루프에서 반복한 후에 오고 여기에 1을 추가합니다. 결국 nums_list의 최대값을 반환하고 있습니다.

class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):

            for j in range(i + 1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

여기서 시간 복잡도는 n제곱이고 공간 복잡도는 n의 o입니다.

4

위의 솔루션으로도 충분하지만 또 다른 접근 방식인 n log는 bisect_left를 사용하여 임시 배열의 왼쪽에 대한 이진 검색을 사용합니다.

from bisect import bisect_left


class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp, n)
            if x == len(tmp):
                tmp.append(n)
            elif tmp[x] > n:
                tmp[x] = n
        return len(tmp)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

출력:

4