JAVA : LIS nlongN 기법

lower_bound 기법

Lower_bound 기법이란 기존 N^2 방식에서 배열 N을 탐색하면서 새로운 벡터 배열에 가장 긴 수를 뽑을 수 있게끔 수들을 저장하는 기법이다.

 

10 20 40 25 20 50 30 70 85 라는 배열이 있다.

 

처음에 벡터에 10을 넣는다.

 

10

10 20

10 20 40

10 20 25

10 20 25

10 20 25 50

10 20 25 30

10 20 25 30 70

10 20 25 30 70 85

 

N까지 탐색하면서 벡터에 들어가는순서를 생각하면 이렇게 된다.

 

벡터에 가장 끝에 담긴수보다 현재 수가 더크면 길이를 증가시키고 추가하면 된다.

 

같은 경우는 버리면 된다.

 

작은 경우는 이진 탐색을 통해서 현재 이값이 지금까지 쌓아온 벡터중에 어디에 들어가야하는가 생각한다.

 

값이 같은 경우가 잇으면 그자리에 대체하면 된다.

 

없다면 현재들어있는 벡터에서 지금 값보다 큰수중 가장 작은 수를 찾는다.

 

이렇게 쌓은수는 경로와 무관하다. 그냥 길이를 뽑기위해서 현재 size에서 가장 최적의 수다.

 

현재 채운 길이가 7이라고한다면 지금 벡터에 담긴 값은 길이 7인 LIS와 무관하다.

 

하지만 8번째 인덱스가 벡터 가장 끝값 보다 크다면  8번째 값은 벡터에 있는 값을 모드 선택하고 자기 자신이 된다는 것을 알수있다.

package com.ssafy.algo;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class test {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("test.txt")));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0;i<N;i++) {
 
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int dp[] = new int [N];
        
        int Lower[] = new int[N];
        int len = 0;
        Lower[0] = arr[0];
        
        for(int i=1;i<N;i++) {
            if(arr[i]>Lower[len]) {
                len+=1;
                Lower[len] = arr[i];
            }else {
                //이진탐색
                int seq = binarySerach(arr[i], 0, len, Lower);
                Lower[seq] = arr[i];
            }
            
        }
        
        System.out.println("최대길이 "+(len+1));
        
    }
    public static int binarySerach(int value,int l,int r,int Lower[]) {
        if(l>r) {
            return l;
        }
        
        int mid = (l+r)/2;
        
        if(Lower[mid] == value) {
            return mid;
        }else if(Lower[mid] > value) {
 
            return binarySerach(value, l, mid-1, Lower);
        }else {
 
            return binarySerach(value, mid+1,r, Lower);
        }
        
        
        
    }
}