최장 증가 부분 수열 (LIS)

1. 문제

  - {3, 2, 6, 4, 5, 1} 다음과 같은 배열에서 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분은? (ex. 2, 4, 5)

  - 부분집합 사용 시 시간복잡도 : O(2 ^ N)

  - 참고 : https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

  - 참고 : https://source-sc.tistory.com/14

[1][LIS : 최장증가수열 알고리즘] - DP 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)

 

---

 

2. DP로 문제 해결

  - 시간 복잡도가 O(N ^ 2)로 이진탐색을 사용해야 한다.

int lis_dp(int n){ // dp를 이용한 lis algorithm
    int i,j;
    int max = 1;
    for(i=0;i<n;i++){
        dp[i] = 1;
        for(j=0;j<i;j++){
            if(arr[j] < arr[i] && dp[j]+1 > dp[i]){
                dp[i] = dp[j]+1;
                if(max < dp[i]){
                    max = dp[i];
                }
            }
        }
    }
    return max;
}

 

---

 

3. DP(이진 탐색)으로 문제 해결

  - 시간 복잡도가 O(n log n)

  - 정확한 수열이 아닌 길이를 구할 때 사용

package com.problem.BOJ;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2565 {
	static Point[] lines;
	static int[] dp;
	static int N;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		lines = new Point[N];
		int count = 0;	// DP의 길이
		int idx = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			lines[i] = new Point(x, y);
		}
		
		Arrays.sort(lines, (p1, p2) -> Integer.compare(p1.x, p2.x));
		
		for (int i = 0; i < N; i++) {
			if (lines[i].y > dp[count]) {
				dp[++count] = lines[i].y;
			} else {
				idx = binarySearch(0, count, lines[i].y);
				dp[idx] =  lines[i].y;
			}
		}
		
		System.out.println(N - count);
	}
	
	public static int binarySearch(int s, int e, int key) {
		int m = 0;
		while (s < e) {
			m = (s + e) / 2;
			if (dp[m] < key) s = m + 1;
			else e = m;	// 들어갈 자리를 찾는 것이기 때문에 -1을 하지 않는다.
		}
		return e;
	}
}