LIS (최장증가부분수열)

LIS(Longest Increasing Subsequence)는 원소가 n개인 배열에서 일부 원소를 골라내어 만든 부분 수열 중에서 모든 원소들이 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열이다. 

 

예시를 들어보자. 

A = {10, 20, 10, 30, 20, 50}인 수열에서 원소가 증가하는 부분 수열은

{10, 20}, {20, 30, 50}, {10, 30, 50} 등이 있는데, 그 중 길이가 최대인 부분 수열은 길이가 4인 {10, 20, 30, 50}이다. 

---

대표 문제는 아래와 같다. 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

 

🕹️ LIS (최장증가부분수열) 알고리즘 과정 

DP 또는 이분탐색을 이용해서 풀 수 있다. 

 

🔹 DP 

일차원 배열로 증가하는 부분 수열의 크기를 나타낸다. 

수열 A = {10, 20, 10, 30, 20, 50}

10	20	10	30	20	50
1	2	1	3	2	4

 

👉 dp[i] 중 최댓값을 출력해주면 된다. 

 

🔸 구현 방법

1. 이중 for 문을 사용하여 해당 원소를 이전의 모든 원소들과 크기를 비교한다.  dp[i] = Math.max(dp[i], dp[j]+1);
2. 해당 원소의 크기가 더 크다면 dp배열을 1 증가시킨다. 
3. 비교를 끝낸 후 dp 배열에서 최댓값을 출력한다. 

---

🔹 이분탐색 

만약, 수열의 크기가 100만 이상이면 DP를 이용해서 풀었을 때 시간초과가 발생한다. 👉 O(n^2)

그러므로 수열의 크기가 클 때는 이분탐색을 이용해야 한다. 👉 O(nlogn)

 

🔸 구현 방법

1. 입력될 수 있는 값보다 작은 수(0)를 배열에 미리 넣어둔다.
2. 입력받은 값이 이전에 입력받았던 값들보다 크다면 배열에 입력받은 값을 넣는다.
3. 반대로 작거나 같다면 이분탐색을 진행해 입력받은 값이 들어갈 자리를 찾는다. 
4. 자리를 찾았으면 기존에 있던 값을 입력받은 값으로 바꾼다. 
5. 처음 넣어둔 0을 제외한 리스트의 사이즈를 출력한다. 👉 리스트 사이즈 -1

ex)

A = {10, 20, 10, 30, 20, 50}

10 입력 ➔ [0 10]

20 입력 ➔ [0 10 20]

10 입력 ➔ [0 10 20]

30 입력 ➔ [0 10 20 30]

20 입력 ➔ [0 10 20 30]

50 입력 ➔ [0 10 20 30 50] 👉 리스트 사이즈 -1 = 4

 

B = {10, 20, 1, 2, 3, 4}

10 입력 ➔ [0 10]

20 입력 ➔ [0 10 20]

1 입력 ➔ [0 1 20]

2 입력 ➔ [0 1 2]

👉 10, 20을 1, 2가 덮어쓴 이유는 20보다 큰 수는 어차피 2보다 크기 때문에 1, 2가 10, 20 이상의 수를 포괄하고 있다고 생각하면 된다. 

3 입력 ➔ [0 1 2 3] 👉 3이 아니라 30이 나와도 배열 가장 마지막에 추가되기 때문에 1, 2로 덮어써도 상관없다. 

4 입력 ➔ [0 1 2 3 4]

 

 

👩‍💻 LIS 구현 코드 

🔹DP 

public class BOJ_11053_가장긴증가하는부분수열 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        int[] dp = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i ; j++) {
                if (A[i] > A[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

 

🔹 이분탐색 

public class LIS_BS{
	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[] arr = new int[n];
        List<Integer> list = new ArrayList<>();
        list.add(0);
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<n; i++){
        	arr[i] = Integer.parseInt(st.nextToken());
            int value = arr[i];
            
            if(value > list.get(list.size()-1)) list.add(value);
            
         	// 값이 작거나 같으면 이분탐색 진행 
            else{
            	int left=0;
                int right = list.size()-1;
              
                while(left < right){
                	int mid = (left+right)/2;
                    if(list.get(mid) < value) left = mid+1;
                    else right = mid;
                }
                
                list.set(right, value); // list에서 원하는 자리에 넣기 
            }
        }
        System.out.println(list.size()-1);
    }
}