BOJ_S2_11053

📁 [S2_11053] 가장 긴 증가하는 부분 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
    static StringTokenizer st;
    static int[] arr, dp;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 수열의 크기
        N = Integer.parseInt(br.readLine());

        // 수열 값 저장
        arr = new int[N];

        // 비교한 값 저장
        dp = new int[N];

        // 처음 값은 0 이다
        int LIS = 0;

        // 배열 입력
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++){

            // dp 배열에 저장될 위치
            int idx = BinarySearch(arr[i], 0, LIS, LIS+1);

            // 못찾은경우
            if(idx == -1){
                dp[LIS] = arr[i];
                LIS++;
            }
            // 찾은 경우
            else{
                dp[idx] = arr[i];
            }
        }
        System.out.println(LIS);
    }

    // 이분 탐색을 통해서 위치 찾기
    public static int BinarySearch(int num, int start, int end, int size) {
        int res = 0;
        while(start<=end){
            // 중앙 값을 찾는다
            int mid = (start+end)/2;

            // 현재 선택된 원소가 해당 원소보다 작거나 같다면 앞부분 탐색
            if(num <= dp[mid]){
                res = mid;
                end = mid-1;
            }
            // 현재 선택된 원소가 해당 원소보다 크다면 뒷 부분 탐색
            else {
                start = mid + 1;
            }
        }
        // dp 테이블에서 삽입될 위치를 못찾은 경우 ( 모든 수들보다 큰 경우 )
        if(start==size){
            return -1;
        }
        // dp 테이블에서 삽입될 위치를 찾은 경우
        else{
            return res;
        }
    }
}

🤔 나의 생각

LIS 알고리즘 문제이다.
이 문제를 풀면서 LIS를 공부하였는데.. 좀 어렵다.
구조는 파악하였는데 내가 이분 탐색을 아직 잘 못해서 그런가 싶기도 하고
그래도 어떤 구존지는 파악해서 만족스러웠다. 좀 더 LIS 문제를 풀어보면서 꺠달아야겠다.
그리고 시간 복잡도가 dp로 풀면 N이 커지면 불가능 하기 때문에 그냥 처음부터 바로 이분 탐색으로 공부를 하였다.
다른 방법으로 하면 한정적이기 때문에 바로 이분 탐색으로 접근하는 것을 추천한다.