최장 증가 부분 수열(LIS, Longest Increasing Subsequence)
최장 증가 부분 수열은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘이다.
예를 들어 주어진 수열이 위와 같을 때 만들어 질 수 있는 증가하는 부분 수열은
위와 같이 같은 색으로 묶인 {2, 4}, {1, 2, 3}, {1, 5, 6} 등 여러가지가 있을 수 있지만
위 그림과 같이 원소 5개로 이루어진 {1, 2, 3, 5, 6}이 수열 A에서 가장 긴 증가하는 부분 수열이다. 이렇게 최장 증가 부분수열을 구하는 알고리즘에 대해 알아보자.
풀이방법
LIS 길이 구하기 - DP: O(n^2)
LIS 길이 구하기 - 이분탐색: O(n log n)
DP를 이용하여 구할 경우 구현이 간단하지만 시간복잡도가 O(n^2)으로 수열의 길이가 길어질수록 효율이 떨어지게 된다.
해당 문제를 해결하기 위해 이분탐색을 이용하는 방법이 있다.
모든 원소에 대하여 LIS를 구하는데 각 원소마다 오름차순으로 들어갈 위치를 이분탐색으로 찾는 방법이다.
LIS의 길이를 length라 했을 때, 시작 단계에서 0으로 초기화를 해준다.
위와 같이 수열이 존재할 때 가장 앞 원소부터 들어갈 위치를 찾는다. A[0]의 경우 LIS의 배열이 비어있으므로 LIS[length]에 들어가게 되고, top = 1이 된다.
LIS[length-1] = 2
length = 1
A[1]인 4는 LIS에 들어간 원소의 가장 마지막 숫자(LIS[length-1] = 2)보다 크기 때문에 LIS 배열에 들어가며 length은 증가하게 된다.
`lis[length++] = A[1];`
LIS[length-1] = 4
length = 2
A[2]=2일 경우, LIS에서 가장 마지막 원소인 4보다 작기 때문에 이분탐색을 통해 A[2]와 같은 숫자이거나 A[2]보다 큰 수 중에 가장 작은 숫자의 위치를 차지하게 된다.
`lis[binarySearch(A[2])] = A[2];`
LIS[length-1] = 4
length = 2
그 다음 원소인 A[3]=1또한 마찬가지로 LIS[top-1]=4보다 작으므로 이분탐색을 통해 들어갈 위치를 찾는다. 같은 숫자가 존재하지 않으므로 A[3]보다 크면서 가장 작은 수인 2의 위치인 LIS[0]을 업데이트 하게 된다.
`lis[binarySearch(A[3])] = A[3];`
LIS[length-1] = 4
length = 2
같은 방법으로 진행할 경우를 설명을 생략하고 그림으로 확인한다면 아래 과정과 같다.
`lis[length++] = A[4];`
length=3
`lis[length++] = A[9];`
length=4
`lis[length++] = A[13];`
length=5
그러므로 LIS의 길이는 5가 된다.
코드
이를 코드로 구현하면 아래와 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int[] lis = new int[N];
int top = 0;
for (int num : A) {
if (top == 0 || lis[top - 1] < num) {
lis[top++] = num;
continue;
}
lis[binarySearch(lis, top, num)] = num;
}
System.out.println(top);
}
private static int binarySearch(int[] lis, int top, int num) {
int start = 0;
int mid = 0;
int end = top;
while (start <= end) {
mid = (start + end) / 2;
if (lis[mid] == num) {
return mid;
} else if (lis[mid] < num) {
start = mid + 1;
} else {
end = mid - 1;
}
}
if (lis[mid] < num) {
return mid + 1;
} else {
return mid;
}
}
}연습문제
[BOJ] 가장 긴 증가하는 부분 수열 2 - https://www.acmicpc.net/problem/12015
-수정중