[DP] LIS ( Longest Increasing Subsequence)

[DP] LIS ( Longest Increasing Subsequence)

2020. 6. 19. 18:03ㆍ알고리즘/동적 프로그래밍

LIS 란 제시된 수열에서 증가된 부분 수열 중 가장 길이가 긴 것을 말한다.

예를 들어보자. 수열 { 1 , 4 , 5 , 2, 3 , 9 , 20, 11 } 이 있다고 하자.

이 중에서 증가 부분 수열은 { 1, 5 , 9 , 11 } 이 될 수도 있고 { 4 , 5 , 9 , 11 } 이 될 수도 있다.

하지만 우리가 찾는 LIS라 불리는 부분수열은 { 1, 4, 5, 9, 11 } 이 될 것이다.

LIS 구현 방법 순서

리스트의 첫 번째 값을 LIS 배열에 넣자.
LIS 배열의 마지막 인덱스 값이 리스트의 값과 비교를 한다.
리스트의 값 > LIS.get(마지막인덱스) LIS 배열 ADD ( 리스트의 값 )
리스트의 값 < LIS.get(마지막인덱스) LIS배열에서 리스트의 값보다 작아지는 최초 인덱스(lower_bound)를 찾자.
2~4를 반복하자.

--------------------------------------- E x a m pl e ---------------------------------------

LIST { 1, 4, 3 , 5 }

1. LIS { 1 } // 리스트의 첫 번째 값을 LIS에 넣어줌.

2. LIS { 1, 4 } // 리스트의 값 > LIS.get(1)

3. LIS { 3, 4 } // 리스트의 값 < LIS.get(1) --> lower_bound = 0

4. LIS { 3, 4, 5 } // 리스트의 값 > LIS.get(2)

---------------------------------------------------------------------------------------------

LIS 구현 방법 2가지.

< 여기서 구현해서 얻는 것은 길이뿐이다. 수열 자체 X>

예시는 백준에 나와있던 2352번 문제 < 반도체 설계 > 로 들어보겠습니다.

1. 완전 탐색

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Integer> list;
    static ArrayList<Integer> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        map = new ArrayList<>();
        for(int i=0; i<N; i++)
        {
            map.add(Integer.parseInt(st.nextToken()));
        }
        list = new ArrayList<>();
        list.add(map.get(0));
        for(int i=1; i<N; i++)
        {
            if(list.get(list.size()-1)<map.get(i)){
                list.add(map.get(i));
            }
            else
            {
                int k = 0;
                for(k=0; k< map.size();k++)
                {
                    if(map.get(i) > list.get(k)) continue;
                    else break;
                }
                list.remove(k);
                list.add(k,map.get(i));
            }
        }
        System.out.println(list.size());
    }
}

2. 이진 탐색을 이용한 최적화

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Integer> list;
    static ArrayList<Integer> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        map = new ArrayList<>();
        for(int i=0; i<N; i++)
        {
            map.add(Integer.parseInt(st.nextToken()));
        }
        list = new ArrayList<>();
        list.add(map.get(0));
        for(int i=1; i<N; i++)
        {
            if(list.get(list.size()-1)<map.get(i)){
                list.add(map.get(i));
            }
            else
            {
                int high = list.size()-1;
                int low = 0;
                int con = 0;
                while(high>=low)
                {
                    int mid = (high+low)/2;
                    int expect = list.get(mid);
                    if(expect < map.get(i))
                    {
                        low = mid+1;
                    }
                    else if(expect >= map.get(i))
                    {
                        con = mid;                       
                        high = mid -1;
                    }
                }
                list.remove(con);
                list.add(con,map.get(i));
            }
        }
        System.out.println(list.size());
    }
}

Dev Room