LIS 알고리즘

DP로 풀면 간단하지만 시간 복잡도가 N^2이 되어서 N이 10000이 넘는 순간 복잡도가 100만이 넘어가면서 문제 제한 시간을 통과하지 못한다.

 

DP로 문제를 해결하는 경우 아래와 같이 이중 for문으로 현재 위치보다 낮은 인덱스 중 가장 큰 dp에 1을 더해서 현재 dp와 비교 후 적용하는 방식으로 진행하면 된다.

 

---

백준 11053

if __name__ == '__main__':     N = int(input())     lst = list(map(int, input().split()))     dp = [1 for i in range(N)]     for i in range(N):         for j in range(i):             if lst[i] > lst[j]:                 dp[i] = max(dp[i],dp[j]+1)     print(max(dp))

 

 

 

 

시간 복잡도 문제를 해결하기 위해서 이분 탐색을 이용하면 된다. 일단은 증가하는 가장 긴 수열의 길이만 구하면 되므로 다음 값이 큰 경우 추가하고 작은 경우 들어갈 인덱스의 값과 대치하면 된다. 예를 들어 10, 20, 30 다음 값이 15일 때 10, 15, 30으로 되는데 뒤에 30은 어차피 이전에 길이가 3인 경우가 있기 때문에 무시할 수 있다는 점이다.

 

 

LIS	탐색값	추가/대치	결과
{10}	20	추가	{10, 20}
{10, 20}	30	추가	{10, 20, 30}
{10, 20, 30}	15	대치	{10, 15, 30}
{10, 15, 30}	20	대치	{10, 15, 20}
{10, 15, 20}	30	추가	{10, 15, 20, 30}
{10, 15, 20, 30}	50	추가	{10, 15, 20, 30, 50}
{10, 15, 20, 30, 50}	40	대치	{10, 15, 20, 30, 40}
{10, 15, 20, 30, 40}	45	추가	{10, 15, 20, 30, 40, 45}
{10, 15, 20, 30, 40, 45}	60	추가	{10, 15, 20, 30, 40, 45, 60}

 

 

이분 탐색이 사용되는 곳은 아래 코드와 같이 대치할 인덱스를 찾을 때 사용된다 해당 알고리즘을 사용하면 시간 복잡도가 n log(n)이 되므로 효율적으로 답을 구할 수 있다. 

 

 

---

백준 12015

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
    static int[] arr;
    static int[] LIS;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        LIS = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        LIS[0] = arr[0];
        int lengthOfLIS = 1;

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            if(key > LIS[lengthOfLIS-1]){
                lengthOfLIS++;
                LIS[lengthOfLIS-1] = key;
            }
            else {
                int min = 0;
                int max = lengthOfLIS-1;
                while(min < max) {
                    int mid = (min + max) / 2;
                    if(LIS[mid] < key) {
                        min = mid + 1;
                    }
                    else {
                        max = mid;
                    }
                }

                LIS[max] = key;
            }
        }
        System.out.println(lengthOfLIS);
    }
}