LIS, 최장 증가 부분 수열이란?
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.
예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 됩니다.
{ 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 입니다.
일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것입니다.
아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다.
for (int i = 0; i < n; i++){
length[i] = 1;
for (int k = 0; k < i; k++){
if (arr[k] < arr[i]){
length[i] = max(length[i], length[k] + 1);
}
}
}주어진 배열에서 인덱스를 하나씩(i+1) 늘려가면서 확인합니다.
그리고 내부 반복문으로 i보다 작은 인덱스들을 하나씩 살펴보면서 arr[k] < arr[i]인 것이 있을 경우, length[i]를 업데이트합니다.
업데이트하는 기준은,
- (1) k번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[i]를 추가했을 때의 LIS 길이와
- (2) 추가하지 않고 기존의 length[i] 값
둘 중에 더 큰 값으로 length[i] 값을 업데이트합니다.
LIS 최적화 방법
위와 같은 방식으로 진행할 시, 시간복잡도는 O(N^2)에 도달합니다.
이런 느린 알고리즘을 최적화 하는 방법은 이분탐색을 활용하는 것 입니다.
시간복잡도를 O(nlog n)으로 줄일 수 있습니다.
관련 문제
참고 블로그
