(Baekjoon) dp - (7) 가장 긴 증가하는 부분 수열_O(NlogN)

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

11053번: 가장 긴 증가하는 부분 수열

 

기존에 하던 방식에서 굳이 자기보다 작은것들을 찾고 거기서 최댓값을 찾기위해 다 검색을 해야하는가?

라는 의문에서 시작하여서 더 빠르게 진행하는 방식으로 이끌어 갈수있다.

 

X,Y테이블을 만든다.

X테이블은 기존하던것처럼 A와 D에관한 테이블이고

Y테이블은 D에관한 테이블이다.

 

table X: (D는 lis)(편의상 i 는 1부터)

i  ㅣ 1 2 3 4 5 6 7 

A ㅣ 6 7 8 2 3 4 5 

D ㅣ 1 2 3 1 2 3 4

 

table Y:

D ㅣ 

A ㅣ

 

D[i] = k가 만족하는 i 중에서 A[i]의 최솟값을 대입하는것이다. 쉽게 설명하면은

X테이블에서 D가 1인 i는 1과 4이다.

i 가 1,4 인 A는 6과 4이다.

이 6과 4중에 가장 작은값 4이다.

그러므로 Y테이블에 이렇게 써준다.

 

table Y:

D ㅣ 1

A ㅣ 4

 

다음으로 D가 2인것은

i가 2,5이고

A에서 7,3이다.

이중 작은값은 3이다.

그러므로

 

table Y:

D ㅣ 1 2

A ㅣ 4 3

 

으로 만들수있다.

 

이런식으로 생성을하면서 진행하는데

자세한것은 나무위키 링크 걸어두었으니 그곳이 과정을 더 자세히 설명되어있으니 참고!!

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2

최장 증가 부분 수열 - 나무위키

이런식으로 테이블을 하나 더 생성하여서 데이터를 만든다면 기존에서 0부터 i-1까지 비교하던과정을

단순히 테이블 Y에서 자신보다 큰값을 찾으면 해당 D값에 + 1을 해주고 해당값을 교체만 해주면된다.

너무너무 간단히 해결이된다.

 

그리고 이 과정에서 테이블 Y에서 자신보다 큰값을 찾는것은 이진탐색으로 진행한다. (최적화)

 

 

약 O(NlogN) 정도로 줄어든다고 한다.

 

우선 위와 같이 아래 코드처럼 데이터를 만들것이다.

 

1) n에서 값을 꺼낸다.

2) n보다 큰값을 list에서 찾기 (lowerbound사용)

lowerbound를 모른다면 참고하자 > 안어려움

https://sudeky.tistory.com/132

(basic) Searching Linear, Binary(upper,lower bound)

3) n보다 큰값이 없다면 list에 추가

4) n보다 큰값이 있다면 비교하여서 큰값을 list.set() 으로 수정

 

package dp;

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

public class _11053_nlogn {

    static int n[] = new int[1001]; // 값 받는것
    static List<Integer> list;

    static int lowerbound(int n){
        int s = 0;
        int e = list.size();
        int m;
        while(s<e){
            m = (s+e)/2;
            if(list.get(m) < n) s = m + 1;
            else e = m;
        }
        return e;
    }
    public static void main(String args[]) throws IOException, NumberFormatException {


        list = new ArrayList<Integer>();
        list.add(0);

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 1; i <= num; i++) {
            n[i] = sc.nextInt();
        }
        int lb;
        for (int i = 1; i < n.length; i++) {
            lb = lowerbound(n[i]);
            if(list.size() == lb)
                list.add(n[i]);
            else{
                if(list.get(lb) > n[i])
                    list.set(lb,n[i]);
            }    

        }

        System.out.println(list.size() - 1);

        sc.close();
    }
}

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study