https://www.acmicpc.net/problem/11053
https://www.acmicpc.net/problem/12015
백준에 있는 문제를 통해서 LIS를 설명해보려고 한다.
저 문제에서 구하고자 하는 것이 바로 LIS이다.
LIS를 구하는 방법에는 DP와 이분탐색이 있다.
먼저 DP로 어떻게 접근할 수 있는지 알아보자
저 배열을 예를 들어 설명하자면
-
DP와 arr를 함께 비교한다.
현재 위치가 i라면 arr[i]인 내 위치 이전에 나보다 작은 arr[i-n]들의 DP 값들을 비교한다. 그 DP 값 중에 가장 큰 값에 더하기 1을 한 것이 DP[i]가 된다.
그 이유는 이미 그 값이 가지고 있는 수열에 현 위치의 arr[i]가 하나 추가되는 것이기 때문이다. -
그러나 내 위치 이전에 나와 같은 arr[i-M]이 존재할 수 도 있다. 그 값이 나보다 작은 arr[i-n]들의 DP 값들을 비교했을 때 max 값일 수도 있다. 그럴 경우에는 그 값과 같은 값을 DP[i]에 저장한다. 왜냐하면 같은 수의 arr[i-M]과 같은 수열을 가지고 있기 때문이다.
-
내 위치 이전에 나와 같은 값이 존재하지도 않고 나보다 작은 배열이 존재하지 않는다면 그냥 1로 저장한다. 순전히 나만 들어간 수열이기 때문이다.
|arr| 10 |20|10|30|20|50|
|DP |1|2|1|3|2|4|
나타내면 아래와 같다.
for(int i=1;i<N;i++){
int max = -1;
int dft=1; // 내 위치 이전 같은값이나 작은값이 존재하지 않은 경우의 기본값
for(int j=i-1;j>=0;j--){
if (arr[i]>arr[j]){//나보다 작은 값
max = Math.max(dp[j],max);}
if(arr[i]==arr[j]){ // 나와 같은 값
dft=dp[j];}
}
if(dft>max) dp[i] = dft; // 나와 같은 값의 dp가 더 큰 경우혹은 내 위치 이전 나보다 작은 값이나 나와 같은 값이 없는 경우
else dp[i]=max+1; // 내 위치 이전 나보다 작은 값들의 dp가 큰 경우
}전체코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st =new StringTokenizer(br.readLine()," ");
int[] arr = new int[N];
int[] dp = new int[N];
dp[0]=1;
for(int i=0;i<N;i++){
int x = Integer.parseInt(st.nextToken());
arr[i]=x;
}
for(int i=1;i<N;i++){
int max = -1;
int dft=1;
for(int j=i-1;j>=0;j--){
if (arr[i]>arr[j]){
max = Math.max(dp[j],max);}
if(arr[i]==arr[j]){
dft=dp[j];}
}
if(dft>max) dp[i] = dft;
else dp[i]=max+1;
}
int max =-1;
for(int i=0;i<N;i++){
max = Math.max(max,dp[i]);
//System.out.println(dp[i]);
}
bw.write(Integer.toString(max));
bw.flush();
bw.close();
br.close();
}
}이제 이분 탐색으로 구하는 방법에 대해서 알아보자
이분 탐색은 길이를 구하고자 하는 문제에만 적합하다.
이분 탐색이 실제 LIS를 구하는 방법은 아니다.
여기서 왜 이분탐색을 사용할까?
이분 탐색은 중간에 대한 지점이 내가 구하고자 하는 값보다 작은가 큰가에 대해 판단해서 범위를 1/2씩 줄여가는 탐색이다. 따라서 앞서 배운 dp보다 더 효율적인다.
여기서 내가 구해놓은 수열에 어떤 위치에 arr의 값이 들어가는 것이 올바를까와 최대한 많은 값을 LIS에 넣기 위한 방법으로 이분탐색을 이용한다.
import java.util.*;
import java.io.*;
public class Main{
static int[] arr;
static int[] LIS;
static int N;
static int binarySearch(int LISlength) {
for (int i = 1; i < N; i++) {
int key = arr[i];
if (LIS[LISlength - 1] < key) {
LISlength++;
LIS[LISlength - 1] = key;
} else {
int lo = 0;
int hi = LISlength;
while (lo < hi) {
int mid = (lo+hi)/2;
if(LIS[mid]>=key){
hi = mid;
}else{
lo = mid+1;
}
}
LIS[lo]=key;
}
}
return LISlength;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
StringTokenizer st =new StringTokenizer(br.readLine()," ");
arr = new int[N];
LIS = new int[N];
for(int i=0;i<N;i++){
int x = Integer.parseInt(st.nextToken());
arr[i]=x;
}
LIS[0]= arr[0];
int result = binarySearch(1);
bw.write(Integer.toString(result));
bw.flush();
bw.close();
br.close();
}
}