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를 유지하면 길이가 4인 증가 부분 수열이 되고, 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입니다(-4, 0, 3, 5도 마찬가지입니다). 첫 번째 요소인 12부터 시작하면 12, 25처럼 값이 두 개만 나옵니다. 최적의 부분 수열은 맨 앞에서 시작할 필요가 없습니다.
제출 시 숨은 테스트 +20개
후속 질문
길이만이 아니라 가장 긴 증가 부분 수열 자체를 반환하면서도 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)가 됩니다. 둘 중 더 큰 값이 답이며, 리스트의 끝을 지나면 더 추가할 수 있는 요소가 없으므로 그때의 결과는 0입니다. 모든 증가 부분 수열은 남기기와 건너뛰기 선택으로 이루어진 하나의 경로이므로, 이 탐색은 최선의 경우를 놓치지 않습니다.
값이 계속 증가하면 두 갈래가 모두 열려 있어 속도가 느립니다. 1, 2, 3, ..., n과 같은 리스트에서는 요소가 하나 늘어날 때마다 호출 수가 두 배가 됩니다. 2의 40제곱은 이미 약 10^12번의 호출이며, 큰 테스트에는 요소가 2500개 있습니다. 하지만 longest(i, prev)는 (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]에서 끝나는 부분 수열의 원소가 둘 이상이라면, nums[i] 바로 앞의 원소는 j < i이고 nums[j] < nums[i]인 어떤 nums[j]이며, 그 원소까지의 부분 수열은 가능한 한 길어야 한다. 따라서 해당 j에 대해 ending[i] = 1 + max(ending[j])이다. 기저 사례: 모든 원소 하나만으로도 부분 수열을 만들 수 있으므로 ending[i]는 1에서 시작한다. 계산 순서: ending[i]는 더 작은 인덱스만 참조하므로 왼쪽에서 오른쪽으로 채운다.
[3, 1, 8, 2, 5, 9, 4, 7]의 경우 표는 [1, 1, 2, 2, 3, 4, 3, 4]이다. 예를 들어 5 앞에는 3, 1 또는 2가 올 수 있으며, 그중 가장 좋은 것은 ending = 2인 2이므로 ending[4] = 3이다. 정답은 마지막 값이 아니라 가장 큰 항목인 4이다. 최적 부분 수열은 어디에서든 끝날 수 있다.
각 인덱스는 앞선 모든 인덱스를 한 번씩 확인하므로, 비교 횟수는 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 길이의 부분 수열이 t에서 끝난다면, 그 부분 수열에는 t보다 작은 값에서 끝나는 k+1 길이의 부분 수열이 포함되어 있기 때문입니다. 따라서 새로운 값 x가 들어올 때마다 ≥ x인 첫 번째 tail을 이진 탐색합니다. 그런 tail이 없다면 x는 모든 tail보다 크므로 가장 긴 부분 수열을 늘릴 수 있습니다. 그러므로 x를 추가합니다. 그렇지 않다면 해당 tail을 x로 바꿉니다. 한 단계 더 짧은 부분 수열은 x보다 작은 값에서 끝나므로, x를 추가하면 끝나는 값이 더 작으면서 길이는 같은 부분 수열이 됩니다.
[3, 1, 8, 2, 5, 9, 4, 7]의 경우 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 자체는 부분 수열이 아닙니다. 의미가 있는 것은 길이뿐입니다. 각 tail이 카드 더미의 맨 위 카드인 카드 게임에서 이름을 따 이 방법을 인내 정렬이라고도 합니다.
각 요소마다 최대 n개의 tail을 대상으로 이진 탐색을 한 번 수행합니다. 가장 큰 입력의 경우 약 2500 × 12 = 30,000단계입니다.
알고리즘
- 빈 리스트
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을 추가하게 되어, 같은 값을 더 긴 부분 수열로 계산합니다. tails를 부분 수열 자체로 취급하는 경우입니다. 그 값들은 서로 다른 부분 수열에서 올 수 있으므로, 부모를 별도로 추적할 때만 출력하세요.- 실수로 연속 구간 버전을 푸는 경우입니다.
[3, 1, 8, 2, 5, 9, 4, 7]에서 이웃한 값들이 계속 증가하는 가장 긴 구간은 2, 5, 9(길이 3)이지만, 정답은 4입니다. - Lua와 R에서는 배열 인덱스가 1부터 시작하므로, 0부터 시작하는
prev = -1마커는 0이 되고 이진 탐색은 인덱스 1부터 현재 크기까지 수행됩니다.
자주 묻는 질문4
최장 증가 부분 수열의 시간 복잡도는 무엇인가요?
tails 메서드는 O(n log n) 시간과 O(n) 공간을 사용합니다. 각 원소마다 이진 탐색을 한 번씩 수행합니다. 모든 인덱스 쌍을 대상으로 하는 동적 프로그래밍 테이블은 O(n²) 시간이 걸리고, 모든 부분 수열을 시도하면 O(2ⁿ) 시간이 걸립니다. n = 2500일 때 각각 약 30,000번, 300만 번, 그리고 천문학적인 횟수의 단계가 필요합니다.
인내 정렬 방법은 왜 올바른 길이를 구할까요?
각 요소를 처리한 후, tails[k]에는 지금까지 확인한 길이 k+1의 증가 부분 수열 중 어떤 것이든 끝날 수 있는 가장 작은 값이 저장됩니다. x가 모든 꼬리 값보다 클 때만 추가되며, 이는 이전의 어떤 부분 수열보다 하나 더 긴 부분 수열이 이제 존재한다는 뜻입니다. 교체는 길이를 바꾸지 않고 끝값만 낮추므로, 목록의 길이는 항상 최장 증가 부분 수열의 길이입니다.
길이뿐만 아니라 실제 최장 증가 부분 수열은 어떻게 구하나요?
각 요소의 부모를 기록하세요. O(n²) 테이블에서 i의 부모는 ending[i]에 값을 부여한 j입니다. tails 방식에서는 각 tail을 이루는 요소의 인덱스를 저장하고, 요소가 배치될 때 부모를 왼쪽 한 위치에 저장된 인덱스로 설정하세요. 그런 다음 가장 긴 부분 수열의 끝에서 부모를 따라 거슬러 올라간 뒤 결과를 뒤집으세요.
대신 가장 긴 비감소 부분 수열을 어떻게 찾나요?
같은 이웃 요소를 허용합니다. 표에서는 nums[j] ≤ nums[i]를 사용합니다. tails 방식에서는 꼬리를 바꿔치기하는 대신 같은 값이 목록을 늘리도록, 크거나 같은 첫 번째 꼬리가 아니라 x보다 엄격하게 큰 첫 번째 꼬리를 찾습니다. 그러면 [7, 7, 7, 7]은 4를 반환합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def lengthOfLIS(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [3, 1, 8, 2, 5, 9, 4, 7]
기대값
4