백준 / 12015 / 가장 긴 증가하는 부분 수열 / java

package K이분탐색;

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class 가장긴증가하는부분수열 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];

        for(int i=0; i<n;i++)
            arr[i] = sc.nextInt();
        sc.close();

        List<Integer> l = new ArrayList<>();
        l.add(arr[0]);

        for(int i=1; i<n;i++){
            int t = arr[i];

            if(t> l.get(l.size()-1)){
                l.add(t);
            } else {
                int start = 0, end = l.size()-1;
                int mid = 0;

                while(start<end){
                    mid = (start + end)/2;

                    if(l.get(mid)>=t)
                        end = mid;
                    else
                        start = mid + 1;
                }
                l.set(start, t);
            }
        }

        System.out.println(l.size());
    }
}

이분 탐색에서 Lower Bound 개념으로 해결해야 하는 문제

이 문제는 이전의 Dp 방식으로는 풀 수 없는 문제이다. 주어진 수열의 크기가 1000000이므로 LIS의 시간복잡도 O(n^2)로 풀기에는 10억이 넘게 되므로 불가능하다.

리스트를 통해 입력받은 배열 값을 저장하는데 현재 배열정보가 리스트의 마지막 값 보다 크다면 리스트에 그 값을 추가하고 그렇지 않은 경우에는 리스트에서 가장 가까운 값을 해당 배열 값으로 변경한다.

가장 가까운 값을 구할 때 이분 탐색을 사용한다.

lower Bound 문제에서 주의할 점은 end의 처음 값을 max - 1 로 하는 것이고 이분 탐색을 통해 구하고자 하는 값은 start로 구하면 된다.
(Upper Bound는 end는 max + 1, 구하고자 하는 값은 start -1로 했었다.)

이렇게 리스트를 수정해 나간 후 마지막으로 리스트의 크기를 출력해서 답을 구할 수 있다.

---

upper, lower에서 start,end를 바꿀 때의 조건도 주의 해야한다.

Upper

if(mid < t)
	end = mid
else
	start = mid + 1

Lower

if(mid >= t)
	end = mid
else
	start = mid + 1

둘이 변경 조건이 완전히 반대인걸 볼 수 있다.
이분 탐색에서 가장 중요한 점은 start와 end를 어떻게 바꿀지 정확히 알고 알고리즘을 사용해야 하는 것이다.