최장 증가 부분 수열이란 말그대로 주어진 수열에서 오름차순으로 구성 가능한 원소들을 선택해서 최대 길이를 찾아내는 것이다.
이분탐색 활용하면 O(NlogN)의 시간복잡도를 갖는다.
예를들어 수열 {10,20,10,30,20,50} 을 보자.
이를 arr[] 배열에 저장하고 dp[] 배열에서 다이나믹프로그래밍 값을 저장한다.
이 때 dp[n]은 n번째 인덱스까지의 값을 탐색했을 때 나올 수 있는 최장 증가 부분 수열의 길이이다.
dp[0] = {10} : 길이 1
dp[1] = {10, 20} : 길이 2
dp[2] = {10} : 길이 1
dp[3] = {10, 20, 30} : 길이 3
dp[4] = {10, 20} : 길이 2
dp[5] = {10, 20, 30, 50} : 길이 4
따라서 dp를 완성하면 위와 같은 결과가 나와야 한다.
단순하게 생각하면 쉽다.
탐색하려는 인덱스에서 이전 위치들을 찾아가면서 해당 값보다 작을 경우 재귀호출을 통해 탐색해나간다.
static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if(dp[N] == null) {
dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for(int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if(seq[i] < seq[N]) {
dp[N] = Math.max(dp[N], LIS(i) + 1);
}
}
}
return dp[N];
}
그냥 이중반복문으로 0~N-1까지 각 원소보다 큰 값들을 카운팅해준다.
for(int i = 0; i < N; i++) {
dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
위의 방법들은 모두 시간복잡도 O(N^2)을 갖는다.
아직 이분탐색을 사용하지 않았기 때문이다!
이 아이디어는 아예 부분수열을 build해가는 과정이다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] seq = new int[N];
int[] LIS = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
LIS[0] = seq[0];
int idx = 1;
for(int i = 1; i < N; i++) {
if(LIS[idx - 1] < seq[i]) {
LIS[idx++] = seq[i];
}
else if(LIS[0] > seq[i]) {
LIS[0] = seq[i];
}
else {
int temp = Arrays.binarySearch(LIS, 0, idx, seq[i]);
LIS[temp < 0 ? -(temp + 1) : temp] = seq[i];
}
}
System.out.println(idx);
}
}