LIS : 최장 증가 수열

LIS : Longest Increasing Subsequence 란?

LIS는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다.

 

 

 

아래 일차원 배열 arr에서 최장 증가 수열을 찾아보자.

int[] arr = {10 20 10 30 20 50};

 

이때, 10 -> 20 -> 30 -> 50 으로 최장 증가 수열의 길이는 4가 된다.

 

 

 

LIS를 구하는 방법은 크게 두가지로 나뉜다.

1. DP 이용 : O(n²))

> dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이

> 모든 i에 대해 0 ~ i-1까지 탐색하며, arr[j] < arr[i] 라면, dp[i] = max(dp[i], dp[j] + 1) 수행

 

 

 

점화식

dp[i] = max(dp[i], dp[j] + 1) // 단, arr[j] < arr[i] (j < i)

 

 

 

예시

int[] arr = {10 20 10 30 20 50};

 

초기 dp 배열 = {1, 1, 1, 1, 1}

 

i = 1

   : arr[i] = 20 > arr[0] = 10 이므로, dp[1] = 2

i = 2

   : arr[2] = 10, 아무것도 10보다 작지 않으므로, dp[2] = 1

i = 3

   : arr[3] = 30, arr[0] = 10이고 arr[2] = 20이므로, dp[3] = 3

i = 4

   : arr[4] = 20 > arr[0] = 10 이므로, dp[4] = 2

i = 5

   : arr[5] = 50 > arr[0], arr[1], arr[3], arr[4] 이므로, dp[5] = 4

 

최종 dp 배열 : {2, 1, 3, 2, 4}로 max(dp) = 4가 된다.

 

 

 

2. 이분 탐색 이용 : (O(n log n))

> List<Integer> list 로 가짜 LIS 수열 후보 생성

> 매 수열을 차례로 보며, 현재 숫자가 list의 마지막 원소보다 크다면, append

>                                                                                         크지 않다면, 이분 탐색으로 교체할 위치를 찾아 치환

 

 

 

예시

int[] arr = {10 20 10 30 20 50};

 

1. 10 -> 빈 리스트 이므로, append -> [10]

2. 20 -> 20 > 10 이므로, append -> [10, 20]

3. 10 -> 10 <= 20 이므로, 이분탐색 : idx=0 후 replace -> [10, 20]

...

 

최종 리스트 : [10, 20, 30, 50]

---

백준 12015번.

이분탐색을 이용해 LIS 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

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

        List<Integer> list = new ArrayList<>();

        for(int i=0; i<N; i++) {
            int num = arr[i];

            if(list.size() < 1) {
                list.add(num);
            } else {
                int idx = binarySearch(list, num);
                if(idx == list.size()) {
                    list.add(num);
                } else {
                    list.set(idx, num);
                }
            }
        }
        System.out.println(list.size());

    }

    private static int binarySearch(List<Integer> list, int num) {
        int left = 0;
        int right = list.size() - 1;

        while(left <= right) {
            int mid = (left+right) / 2;

            if(list.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

}

 

Longest Increasing Subsequence

Longest Increasing Subsequence

Longest Increasing Subsequence