[알고리즘]백준 12015: 가장 긴 증가하는 부분수열(LIS)

가장 긴 증가하는 부분수열(LIS)

 

 

가장 긴 증가하는 부분 수열을 구하기 위해 아래와 같이 DP를 이용해서 풀 수 있지만, 이 경우 시간복잡도가 O(N^2)이기 때문에 N값이 매우 커지면 위험하다고 생각했다.

//1. dp
for(int i=0; i<N; i++){
    for(int j=0; j<i; j++){
        if(A[i]>A[j]) dp1[i] = Math.max(dp1[i],dp1[j]+1);
    }
}

 

이분탐색, O(logN)

이분탐색을 이용하면 DP를 이용했을 때 O(N^2)이었던 시간복잡도를 O(NlogN)으로 줄일 수 있다.

public static void binarySearch(List<Integer> arr, int target){
	int left = 0;
	int right = arr.size()-1;
	
	while(left<=right){
		int mid = (left+right)/2;
	
		if(arr.get(mid)>=target){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
	
	return left;
}

⇒ target이 존재하면, target이 존재하는 idx를 return하고, 존재하지 않는다면 target을 삽입할 수 있는 idx를 return한다.

List<Integer> list = new ArrayList<>();
for(int i=0; i<N; i++){
    int pos = binarySearch(list, A[i]);

    // pos 위치에 값 업데이트 또는 새로운 값 추가
    if (pos < list.size()) {
        list.set(pos, A[i]);
    } else {
        list.add(A[i]);
    }

}

binarySearch를 통해서 해당 원소를 삽입할 수 있는 위치를 return 받고, pos의 위치에 원소를 갱신/삽입한다. list 배열은 항상 증가하는 상태로 유지되며, 이를 통해 가장 긴 증가하는 부분 수열의 길이를 구할 수 있다.

 

코드

//616ms
import java.io.*;
import java.util.*;

public class Main_12738_G2_LIS3 {
    static int N;
    static int[] A;

    public static int binarySearch(List<Integer> arr, int target){
        int left = 0;
        int right = arr.size()-1;

        while(left<=right){
            int mid = (left+right)/2;

            if(arr.get(mid)>=target){
                right = mid-1;
            }else if(target>arr.get(mid)){
                left = mid+1;
            }
        }

        return left;
    }

    public static void main(String[] args) throws IOException {
        //0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        A = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());

        //1. 로직
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            int pos = binarySearch(list, A[i]);

            // pos 위치에 값 업데이트 또는 새로운 값 추가
            if (pos < list.size()) {
                list.set(pos, A[i]);
            } else {
                list.add(A[i]);
            }

        }

        //2. 출력
        System.out.println(list.size());
    }
}

 

 

 

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