[20210626] LIS(최장 증가 부분 수열)
최장 증가 부분 수열에 대해 알아보자.
LIS(Longest Increasing Subsequence)
숫자로 이루어진 배열의 일부 원소를 선택해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순 정렬이 되어 있으면서 가장 긴 수열을 최장 증가 부분 수열이라 한다. 이 문제는 DP로 풀 수 있는 유명한 알고리즘이다.
예시
{2,5,3,7,1,2,8} 라는 수열이 있다.
여기서, 만들어지는 최장 부분 수열은 {2,5,3,7,1,2,8}, {2,5,3,7,1,2,8}로, {2,5,7,8}, {2,3,7,8}로 총 2개이다. 이처럼 하나의 수열에서 최장 부분 수열은 여러 개가 나올 수도 있다. 그래서 보통은 최장 부분 수열 자체를 찾는 문제보다는 최장 부분 수열의 길이를 묻는 문제가 많다.
문제
https://www.acmicpc.net/problem/11053 - 가장 긴 증가하는 부분 수열
O(N^2^) 알고리즘
우선 해당 문제는 DP를 이용하여 풀 수 있다. DP 배열로 1차원 배열이 필요하다. DP[i] : i 번째 원소를 마지막 값으로 갖는 LIS의 길이
for(int i = 0; i < N; i++) {
for(int j = 0; j < i; j++) {
if(Arr[i] > Arr[j]) {
DP[i] = max(DP[i], DP[j] + 1);
}
}
}
해당 알고리즘은 매 인덱스 마다 이전의 모든 배열의 요소와 비교하기 때문에 N^2^알고리즘이 된다.
O(NlogN) 알고리즘
이전의 모든 배열의 요소와 비교하는 부분을 이진 탑색으로 최적화하면 N 을 logN으로 바꿀 수도 있다.
그러기 위해서는 DP의 용도를 조금 바꿀 필요가 있다.
DP를 LIS 수열로 갱신한다. DP[i] : LIS 수열의 i 번째 요소로 기존의 DP 값보다 작은 값이 나오면 갱신해준다. ex) {2, 1, 3, 4}에서는
2 일때, LIS = {2} 1 일때, LIS = {1} 처럼 기존의 2보다 1이 더 작다면 갱신해주면서 LIS 수열을 만들어간다.
if(DP[j] < Arr[i]) {
DP[j + 1] = Arr[i];
} else {
DP[binarySearch(Arr[i])] = Arr[i];
}
해당 인덱스에 대한 검색이 N에서 logN으로 변형되어서 전체 알고리즘 성능은 O(NlogN)이 된다.