[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());
}
}