search

WonYong-Jang / algorithm

0 stars 0 forks source link

LIS / ( lower_bound , upper_bound ) #23

Open WonYong-Jang opened 5 years ago

WonYong-Jang commented 5 years ago

N^2 방법

dp[i] = data[i] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이

for(int i=1; i<= N; i++)
{
    for(int j=0; j < i; j++)
    {
        if(data[i] > data[j] && dp[i] < dp[j] + 1)
        {
            dp[i] = dp[j] + 1;
        }
    }
    result = max(result, dp[i]);
}
System.out.println(result);

Lower Bound 를 이용한 방법 / nlogn

dp 는 길이가 x인 최장증가수열의 마지막 수의 최소값을 의미

ex ) 10, 20, 40, 30, 70, 50, 60

1) 처음값 10을 넣어줌 : 배열의 최대 배열 사이즈 1 2) 20 값은 배열 마지막 값인 10보다 크므로 배열 뒤에 추가 : 배열 사이즈 2 3) 40 추가 : 배열 사이즈 3 / (10, 20, 40) 4) 30 값은 배열의 마지막 값인 40보다 작으므로 lower_bound 를 이용하여 40자리에 30을 치환 / (10,20, 30) 5) 70 추가 : 배열 사이즈 4 ( 10, 20, 30, 70) 6) 50 값을 70과 치환 (10, 20, 30, 50) : 배열사이즈 4 7) 60 추가 : 배열 사이즈 5 (10, 20, 30, 50, 60)

고려해야 할 부분

size = 1;
dp[1] = data[1];
for(int i=2; i<= N; i++)
{
    if(data[i] > dp[size]) // dp 맨뒤에 있는 자리와 비교하여 더 큰값이면 이어 붙이기  
    {
        dp[++size] = data[i];
    }
    else if(data[i] < dp[size])
    {
        int tdx = lower_bound(1,size,data[i]);
        dp[tdx] = data[i];
        }
    }
}
System.out.println(size);

lower_bound 방식 ( lis 요소들 추적 가능한 방법! )

실제 lis 배열을 구하는 알고리즘을 보자 예를들면 다음과 같다. 1 6 2 5 7 3 5 6인 경우 ans배열에는 다음과 같이 들어간다. dx :: 0 1 1 2 3 2 3 4 dy :: 1 6 2 5 7 3 5 6
이 값을 dx를 기준으로 뒤에서 부터 조사해오면 dx가 4일때 (6) - > dx가 3일때 (5) -> dx가 2일때 (3) -> dx가 1일때 (2) -> dx가 0일때(1)이다.

이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.

public class baek14002 {

    static int N;
    static int[] data = new int[1005];
    static int[] dp = new int[1005];
    static Node[] ans = new Node[1005];
    static Deque<Integer> que = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<= N; i++)
        {
            data[i] = Integer.parseInt(st.nextToken());
            ans[i] = new Node(-1,-1);
        }

        dp[1] = data[1];
        ans[1].dx = 1; // 실제 인덱스 1로 처음 시작 
        ans[1].dy = dp[1]; // 실제 값 
        int size = 1;
        for(int i=2; i<= N; i++)
        {
            if(dp[size] < data[i])
            {
                dp[++size] = data[i];
                ans[i].dx = size;
                ans[i].dy = data[i];
            }
            else {
                int idx = lower_bound(1, size, data[i]);
                dp[idx] = data[i];
                ans[i].dx = idx;
                ans[i].dy = data[i];
            }
        }
        System.out.println(size);
        // 인덱스 i=2 부터 계속 해서 업데이트 해왔으므로
        // 맨뒤 인덱스 부터 찾아 나감 
        int t = size;
        for(int i = N; i > 0; i--)
        {
            if(t == ans[i].dx)
            {
                que.addLast(ans[i].dy);
                t--;
            }
        }

        while(!que.isEmpty())
        {
            int num = que.pollLast();
            System.out.print(num+" ");
        }
    }
    static class Node {
        int dx, dy;
        Node(int a, int b) {
            dx=a; dy=b;
        }
    }
}

lower_bound 란?

인덱스 트리를 이용한 방법 / nlogn

설명 : https://m.blog.naver.com/kks227/220791986409 (그림 확인)

주의 사항

WonYong-Jang commented 5 years ago

함정 문제

백준 11055번 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055

7570번: 줄세우기 https://www.acmicpc.net/problem/2631

LIS 문제 모음 : https://github.com/hotehrud/acmicpc/tree/master/algorithm/lis

WonYong-Jang commented 5 years ago

Lower_bound

원하는 값 k 이상의 값이 처음으로 나오는 인덱스를 리턴

주의 ! : 만약 모든 원소가 k 보다 작으면 n+1 을 출력하게 되는데 그렇기 때문에 !!!

===> 처음 구간을 잡을때 [1,n+1] 로 잡을것!!!!!!!!!!!!!!!!! ex1) 1 3 5 7 7 / target : 7 일 때 ==> 4번째 인덱스 리턴 ex2) 1 2 3 5 7 9 11 15 / target : 6 일때 ==> 5번째 인덱스 리턴 ex3) 1 2 3 4 5 / target : 7 일때 ==> 6번째 인덱스 출력 ( n + 1 )

public static int lower_bound(int s, int e, int target)
{
    int mid =0;
    while( s < e)
    {
        mid = (s + e) / 2;
        if(data[mid] < target) {
            s = mid + 1;
        }
        else {
            e = mid;
        }
    }
    return e;
}

Upper_bound

원하는 값 k를 초과한 값이 처음 나오는 인덱스 리턴

public static int upper_bound(int s, int e, int target)
{
    int mid =0;
    while( s < e)
    {
        mid = (s + e) / 2;
        if(data[mid] <= target) {
            s = mid + 1;
        }
        else {
            e = mid;
        }
    }
    return e;
}