ps:가장_긴_증가하는_부분_수열
목차
가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)
기본 풀이 방법
- 가장 기본이 되는 문제 형태는 LIS의 길이를 구하는 것이다.
- 대충 세가지 방법이 있다
- DP를 이용하는 방법. O(n^2)
- 세그먼트 트리를 이용하는 방법. O(nlogm)
- 이진탐색을 이용하는 방법. O(nlogn)
- 기본적인 방법은 DP를 이용해서 푸는 것이다. dp[i]를 A[i]를 마지막 값으로 갖는 LIS의 길이라고 하자. 점화식은 간단하게 나온다.
- dp[i] = max_(j<i, A[j]<A[i]){dp[j]} + 1
- 이 점화식을 이용해서 dp table을 채운 다음에, 최댓값을 찾으면 된다. table을 채우는 데에는 O(n^2)이 걸린다.
- 세그먼트 트리를 사용하는 방법은 이 점화식을 조금 더 쉽게 계산할수 있게 한 것이다.
- 위의 방법에서 O(n^2)이 걸리는 이유는 dp[i]를 계산하기 위해서 dp[1…j]의 값을 모두 비교해서 A[j]<A[i]인 것 중에서 최댓값을 찾기 때문이다. 즉 한 칸을 채우는데에 O(n)이 걸리기 때문에 전체가 O(n^2)이 걸리는 것인데, 구간 쿼리의 방법을 이용하면 최댓값을 찾는 것을 좀더 빠르게 할 수 있다. A[i]로 끝나는 LIS의 길이를 dp[i]에 저장하는 대신에, X[A[i]]에 저장한다고 생각하자. 즉, X[A[i]] = dp[i] 인 X를 만들고, dp 대신 X에서 찾고 업데이트 하도록 하자. A[j]<A[i] 인 j중에서 dp[j]의 최댓값은 max(X[0:A[i]]) 으로 구할수 있다. 이것은 최댓값 세그먼트 트리를 이용하면 O(i)가 아니라, O(log(A[i])) 에 구할 수 있다. A의 원소의 최댓값을 m이라고 하면 O(logm)이다. 업데이트 역시 O(logm). 그러면 전체를 계산하는 것은 O(nlogm)이 된다.
- m이 n보다 많이 큰 경우에는 좌표압축을 사용하거나, 다이나믹 세그먼트 트리를 이용해서 O(nlogm)을 O(nlogn)으로 줄일 수있다. (많은 강좌에서는 이 설명이 빠져있는 채로 처음부터 시간 복잡도를 O(nlogn)으로 설명하고 있다..)
- 이진탐색 방법도 max_(j<i, A[j]<A[i]){dp[j]} 를 빠르게 구하는 방법이다… [작성 예정]
- O(n^2) 방법은 속도가 느려서 실제로 쓸일은 없다. 두가지의 O(nlogn) 방법중에서는 세그먼트 트리 방법이 좀더 떠올리기에는 간단하다. 그러나 이진탐색 방법이 속도도 더 빠르고 메모리도 적게 먹고 구현도 짧다.
- 그래서, 관련 응용 문제들을 풀 때에도, 가능하면 세그먼트 트리를 안 쓰는 솔루션으로 풀도록 하겠다.
- 각 방법에 대한 자세한 설명은 https://cp-algorithms.com/sequences/longest_increasing_subsequence.html 참고.
- 저 방법들은 기본적으로 LIS의 길이를 구하는데 쓰이지만, 코드를 조금 수정해서 시퀀스를 복원하는 것도 간단하다.
- 나중에 알게되었는데, 세그먼트 트리를 이용해서 O(nlogn)에 구하는 다른 방법도 존재한다. 설명은 생략
코드
- 길이 구하기
def lis_length(seq): arr = [] for val in seq: pos = bisect.bisect_left(arr, val) if pos == len(arr): arr.append(val) else: arr[pos] = val return len(arr)- 아래와 같이 바꾸면 bisect횟수를 줄여서 사소한 최적화가 가능하다
def lis_length(seq): arr = [seq[0]] for val in seq: if val > arr[-1]: arr.append(val) else: arr[bisect.bisect_left(arr, val)] = val return len(arr)
- 중복값을 포함하는 수열, 즉 non-decreasing sequence 를 구하는 경우는 bisect_left를 bisect_right로 바꿔주면 된다
- decreasing sequence 를 구하려면, bisect가 커스텀 비교 연산자를 지원 안하는 관계로, 그냥 num 에 -를 붙여서 계산하는 것이 간편하다.
- 또는, 그냥 수열을 역순으로 이터레이트하면서 lis를 구해도 된다
- 세그먼트 트리로 푸는 방법은 가장 긴 증가하는 부분 수열 참고.
관련 문제
- 가장 긴 증가하는 부분 수열 길이 구하기. n<1,000
- 가장 긴 증가하는 부분 수열 2 길이 구하기. n<1,000,000
- 가장 긴 증가하는 부분 수열 4 시퀀스 구하기. n<1,000
- 가장 긴 증가하는 부분 수열 5 시퀀스 구하기. n<1,000,000
응용
LIS의 갯수를 구하기
- https://cp-algorithms.com/sequences/longest_increasing_subsequence.html 에서는 이분탐색 방법으로는 불가능하고 세그먼트 트리 방법에서만 가능하다고 나와있지만, 실제로는 이분탐색 방법에서도 가능하다.
- [To be filled]
2-element tuple
- [To be filled]
3-element tuple
- [To be filled]
- 2d-segment tree를 쓰는 것이 직관적
- 하지만 더 효율적인 것은 https://chw0501.tistory.com/24
최소 갯수의 non-increasing subsequence 로 배열을 커버하기
- 배열을 커버하는 non-increasing subsequence의 최소 갯수는 longest increasing subsequence 의 길이와 같다.
- 같은 개념으로, 배열을 커버하는 increasing subsequence의 최소 갯수는 longest non-increasing subsequence 의 길이와 같다.
- 위의 증명이 보고 이해하기 어렵지는 않지만, 막상 떠올리려면 잘 떠오르지 않을때도 있는데.. 딜워스의 정리를 공부하고 나서 보니 이것도 딜워스의 정리의 특정 케이스로 생각할수 있는 것 같다.
- 딜워스의 정리는 부분순서집합에서 최소 경로 커버의 크기와 최대 반사슬의 크기가 같다는 정리이다.
- LIS문제를 이렇게 생각해보자. (인덱스, 값)을 노드로 보고, 인덱스와 값이 모두 큰 노드쪽으로 파셜 오더가 있다고 생각하면 부분순서집합이 된다. 부분순서집합을 DAG로 변환하면, LIS를 찾는 것은 가장 긴 패스를 찾는것이 되고, 최소갯수의 increasing subsequence 로 모든 배열을 커버하는 것은 최소 경로 커버를 구하는 것이 된다. 또한 이 노드들의 부분집합중 위상관계가 없는 노드의 집합중 가장 큰 것 (=최대반사슬) 은 longest non-increasing subsequence 라는 것을 쉽게 이해할 수 있다.
- 원래 이 정리는 이분 매칭을 공부하다가 보게 되었다. 부분순서집합에서 최소 경로 커버의 크기를 이분매칭으로 구하는 방법이 존재한다. 딜워스의 정리를 이용하면 최대 반사슬의 크기도 이분매칭으로 구할 수 있게 된다.
- 다만 여기에서 는 반대로, 최대 반사슬의 크기가 LIS의 길이와 같아서 이쪽을 더 쉽게 구할 수 있으므로, 이 결과를 이용해서 최소 경로 커버의 크기를 빠르게 구하는 데에 사용된다.
- 바꿔 말하면 '최소 갯수의 non-increasing subsequence 로 배열을 커버하는 문제'를 이분 매칭으로도 풀수 있기는 하다는 말이다. 시간복잡도가 O(n^2.5)가 되므로 비효율적이라서 그렇지..
- 관련 문제
ps/가장_긴_증가하는_부분_수열.txt · 마지막으로 수정됨: 2023/08/18 06:56 저자 teferi
토론