Longest Increasing Subsequence
정수 목록 nums가 주어집니다. 부분 수열은 일부 요소를 원래 순서대로 유지하고 나머지는 버리는 것으로, 유지된 요소들이 서로 인접할 필요는 없습니다. 왼쪽에서 오른쪽으로 값이 엄격하게 증가하는 가장 긴 부분 수열의 길이를 반환하세요. 연속된 두 값이 같으면 증가하는 것으로 간주하지 않습니다.
함수
- numsinteger-array
- 선택할 정수 목록
- 반환값integer
- 가장 긴 엄격한 증가 부분 수열의 길이
제약 조건
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
예제
- 입력
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- 출력
- 4
- 설명
- 1, 2, 5, 9는 증가하며, 1, 2, 5, 7과 1, 2, 4, 7도 마찬가지입니다. 길이는 4입니다. 다섯 개의 값을 선택해 계속 증가하게 할 수는 없습니다.
- 입력
- nums = [7, 7, 7, 7]
- 출력
- 1
- 설명
- 값은 엄격하게 증가해야 하므로, 7 두 개가 같은 부분 수열에 있을 수 없습니다. 원소 하나만으로도 부분 수열이 되므로 답은 1입니다.
- 입력
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- 출력
- 4
- 설명
- -4, 0, 3, 16의 길이는 4입니다. 첫 번째 요소인 12부터 시작하면 12, 25와 같이 값이 두 개밖에 나오지 않습니다. 최적의 부분 수열은 맨 앞에서 시작할 필요가 없습니다.
후속 질문
길이와 함께 가장 긴 증가 부분 수열 자체도 반환하면서, 여전히 O(n log n) 시간에 실행할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
전체 목록에서 가장 좋은 부분 수열을 직접 설명하기는 어렵습니다. 각 인덱스
i에 대해 더 범위를 좁힌 질문을 해 보세요.nums[i]로 정확히 끝나는 가장 긴 증가 부분 수열은 무엇일까요?nums[i]에서 끝나는 부분 수열은nums[i]하나만으로 이루어지거나, 이전의 어떤nums[j] < nums[i]에서 끝나는 최적의 부분 수열을 이어서 구성됩니다. 그런j중 최적의 것을 선택하고 1을 더합니다. 정답은 끝나는 위치와 관계없이 이러한 값들 중 가장 큰 값입니다.O(n²)보다 더 낮은 시간 복잡도를 얻으려면, 각 길이마다 그 길이의 부분 수열이 끝날 수 있는 가장 작은 값을 유지하세요. 이 값들은 정렬된 상태를 유지하므로, 이진 탐색을 통해 새로운 숫자가 가장 긴 부분 수열을 늘리는지 아니면 끝값을 대체하는지 알 수 있습니다.
풀이
n개의 숫자로 이루어진 목록에는 2^n개의 부분 수열이 있으므로, 모두 확인하기에는 너무 많습니다. 각 인덱스마다 그 위치에서 정확히 끝나는 최장 증가 부분 수열의 길이를 구하면 O(n²) 크기의 표가 만들어집니다. 가장 빠른 방식은 각 길이마다 해당 길이의 부분 수열이 끝날 수 있는 가장 작은 값을 저장하고, 이진 탐색으로 각 원소를 배치합니다.
모든 요소를 선택하거나 건너뛰기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 요소를 유지할지 결정하세요. nums[i]는 마지막으로 유지한 값보다 클 때만 유지할 수 있습니다. longest(i, prev)는 마지막으로 유지한 요소가 prev에 있을 때(또는 -1일 때), 인덱스 i부터 계속 추가할 수 있는 요소의 최대 개수입니다. 건너뛰면 longest(i+1, prev)가 되고, 유지하면 1 + longest(i+1, i)가 됩니다. 모든 증가 부분 수열은 이러한 선택으로 이루어진 하나의 경로입니다.
1, 2, 3, ..., n에서는 두 분기 모두 계속 열려 있으므로 요소가 추가될 때마다 호출 수가 두 배로 늘어납니다. 2^40은 이미 약 10^12입니다. 하지만 서로 다른 (i, prev) 쌍은 최대 n²개입니다.
알고리즘
prev가 마지막으로 유지한 요소의 인덱스이거나-1일 때,longest(i, prev)를 작성하세요.i가 끝을 지나면 0을 반환하세요.nums[i]를 건너뛰세요:best = longest(i+1, prev).prev가-1이거나nums[i] > nums[prev]이면 해당 요소를 유지하세요:best = max(best, 1 + longest(i+1, i)).best를 반환하세요. 답은longest(0, -1)입니다.
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)각 인덱스에서 끝나는 가장 긴 부분 수열
핵심 아이디어
ending[i]를 마지막 원소가 nums[i]인 가장 긴 증가하는 부분 수열의 길이라고 하자. nums[i] 앞에 오는 원소가 있다면, 그것은 j < i이고 nums[j] < nums[i]인 어떤 nums[j]이며, 그 원소까지의 부분 수열은 가능한 한 길어야 한다. 따라서 해당하는 j에 대해 ending[i] = 1 + max(ending[j])이고, 그런 원소가 없으면 1이다. 왼쪽에서 오른쪽으로 채운다.
[3, 1, 8, 2, 5, 9, 4, 7]의 표는 [1, 1, 2, 2, 3, 4, 3, 4]이다. 5 앞에는 3, 1 또는 2가 올 수 있고, 그중 길이가 가장 긴 부분 수열의 길이는 2이므로 ending[4] = 3이다. 최적의 부분 수열은 어디서든 끝날 수 있으므로 답은 가장 큰 값이다.
n(n-1)/2번 비교한다. n = 2500일 때 약 3.1 × 10^6번이다.
알고리즘
- 모든 항목을 1로 설정하여
ending을 만드세요. - 왼쪽에서 오른쪽으로 각
i에 대해 모든j < i를 살펴보세요. nums[j] < nums[i]이면, 더 큰 값일 때ending[i]를ending[j] + 1로 설정하세요.ending에서 가장 큰 값을 반환하세요.
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)이진 탐색을 사용한 최소 꼬리
핵심 아이디어
모든 길이에 대해, 해당 길이의 증가 부분 수열이 끝날 수 있는 값 중 가장 작은 값만 유지합니다. 길이 k+1에 해당하는 값은 tails[k]입니다. 끝값이 더 작아도 결코 불리하지 않습니다. 9 뒤에 올 수 있는 값은 5 뒤에도 올 수 있습니다. tails는 계속 엄격한 오름차순을 유지합니다. 길이 k+2인 증가 부분 수열의 마지막 값을 제거하면, 그보다 낮은 값으로 끝나는 길이 k+1인 부분 수열을 얻을 수 있기 때문입니다.
각 x에 대해 첫 번째 꼬리값 ≥ x를 이진 탐색합니다. 그런 값이 없으면 x를 추가합니다. 가장 긴 부분 수열을 확장하기 때문입니다. 그렇지 않으면 해당 꼬리값을 x로 바꿉니다. 한 단계 짧은 부분 수열은 x보다 작은 값으로 끝나므로, x를 사용하면 같은 길이를 더 작은 끝값으로 만들 수 있습니다.
예제 1에서 tails는 [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]로 바뀝니다. 길이는 4입니다. [1, 2, 4, 9]에서 4는 9 뒤에 나왔으므로, tails의 길이만 의미가 있습니다.
알고리즘
- 빈 리스트
tails로 시작합니다. nums의 각x에 대해,tails[k] ≥ x를 만족하는 첫 번째 인덱스k를 이진 탐색합니다.≥ x인 꼬리가 없으면x를 추가합니다.- 그렇지 않으면
tails[k] = x로 설정합니다. tails의 길이를 반환합니다.
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
함정과 경계 사례
- 가장 큰 항목 대신
ending[n-1]을 반환하는 것.[1, 2, 3, 0]에서 마지막 항목은 1이지만, 정답은 3입니다. <대신≤와 비교하는 것.[7, 7, 7, 7]은 4가 아니라 1을 반환해야 합니다.- tails 버전에서
≥ x대신 첫 번째> x인 꼬리를 찾는 것. 그러면 두 번째 7이 첫 번째 7 뒤에 추가되어, 같은 값도 증가하는 것으로 계산됩니다. - 실수로 연속된 버전을 푸는 것. 예시 1에서 이웃한 값으로 이루어진 가장 긴 증가 구간은 2, 5, 9(길이 3)이지만, 정답은 4입니다.
- 배열이 1부터 시작하는 Lua 또는 R에서 0 기반 인덱스를 사용하는 것.
prev = -1표시는 0이 되고, 이진 탐색은 인덱스 1부터 현재 크기까지 실행됩니다.
자주 묻는 질문3
최장 증가 부분 수열의 시간 복잡도는 무엇인가요?
tails 메서드는 O(n log n) 시간과 O(n) 공간을 사용합니다. 각 요소마다 이진 탐색을 한 번씩 수행합니다. 모든 인덱스 쌍을 대상으로 하는 표는 O(n²) 시간이 걸리고, 모든 부분 수열을 시도하면 O(2ⁿ)이 걸립니다.
최장 증가 부분 수열에서 patience sorting이란 무엇인가요?
이는 카드 게임의 이름을 딴 tails 메서드입니다. 각 꼬리는 더미의 맨 위 카드입니다. 카드는 맨 위 카드의 값이 자신의 값 이상인 가장 왼쪽 더미에 놓이거나 새 더미를 시작합니다. 더미의 개수가 정답입니다.
대신 가장 긴 비감소 부분 수열은 어떻게 찾나요?
같은 값을 가진 이웃을 허용합니다. 표에서는 nums[j] ≤ nums[i]를 사용하세요. tails 방식에서는 x보다 엄격히 큰 첫 번째 꼬리를 검색하여, 같은 값은 꼬리를 대체하는 대신 리스트를 확장합니다. 그러면 [7, 7, 7, 7]은 4를 반환합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def lengthOfLIS(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
nums = [3, 1, 8, 2, 5, 9, 4, 7]
예상 출력
4