BOJ 12015 - 가장 긴 증가하는 부분 수열 2

 

단계별 풀어보기 DP단락에 있는 BOJ 11053 - 가장 긴 증가하는 부분 수열과 동일한 문제입니다.

다만 입력값의 범위가 크게 늘어난 만큼, 풀이 방법에 개선이 필요합니다.

 

먼저 입력이 1 <= N <= 1000인 BOJ 11053의 풀이입니다.

public class Main {
    static int[] dp;
    static int[] arr;
    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];

        StringTokenizer 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[i] = 1;
            for(int j = 0; j<i; j++){
                if( arr[i] > arr[j] ){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }

        Arrays.sort(dp);

        System.out.println(dp[N-1]);
    }
}

 

반복문 안에서 (1 + N) * N / 2번의 연산이 일어납니다.

입력 범위가 작기 때문에 N = 1000인 경우에도 N^2 단위의 순회가 일어나도 풀이에 큰 문제가 없었습니다.

그러나 위 풀이를 그대로 이번 문제에 적용한다면 N^2의 최댓값이 1조가 되므로 요구 시간의 10배를 줘도 통과할 수 없게 됩니다.

 

시간 단축을 위해 몇 가지 테스트를 진행해 보았습니다.

먼저 주어진 예제로 시작합니다.

예제 1번

 

N^2을 피하기 위해 전체 데이터 순회 N번에서 할 수 있는 행동을 생각해 봤습니다.

• 부분 수열의 길이가 마지막으로 늘어난 위치(lastIndex)를 기억한다.
• 탐색한 값이 마지막 증가값보다 크면, lastIndex를 갱신하고 최대 길이를 1 늘려준다.

 

예제에선 성공하는 것처럼 보이지만, 당연하게도 큰 값이 중간에 있다면 제대로 작동하지 않습니다.

반례

예를 들어 입력 데이터가 [ 20, 10, 50, 10, 20, 30 ]인 경우를 생각하면

증가하는 부분수열의 최대 길이는 [ 10, 20, 30 ]의 3이 되어야 하는데

최댓값인 50 이후로는 부분수열의 길이가 갱신되지 않는 문제가 생깁니다.

 

index = 5에서 30을 만났을 때 최대 길이는 2에서 3으로 증가되어야 합니다.

그렇다면 이전까지 최대 길이가 2가 되는 부분수열을 찾아봅니다.

[ 20, 50 ], [ 10, 50 ], [ 10, 20 ], [ 10, 20 ]인 4가지 경우가 존재합니다.

여기서 길이가 더 늘어날 수 있는 건 끝 값이 20으로 끝나는 두 가지 경우입니다.

직전 증가값이 작을수록 더 긴 길이를 가지는 데 유리합니다.

 

길이가 3이 되기 위한 최선의 경우를 따져봤으니

다시 길이가 2가 되기 위한 길이가 1인 경우를 따져볼까요?

모든 엘리먼트에서 본인이 시작점일 때 부분 수열의 길이는 1이 됩니다.

여기서 최대 길이가 30이 될 수 있는 경우는 출발점이 10인 index 1, 3

즉 2,4번째 이미지에서만 정답으로 진행할 수 있습니다.

 

즉, 특정 길이를 가지기 위한 값이 작을수록 긴 부분수열을 가지기 유리합니다.

그렇다면 dp배열의 역할을 길이 n에 대응하는 최솟값 저장으로 바꿔보겠습니다.

 

로직도 구성을 달리해보죠.

length를 현재까지 찾은 최대 부분수열의 길이라고 하고 간편하게 len으로 표기하겠습니다.

• arr[i]의 값이 dp[len]보다 큰 경우에만 dp[len+1]에 해당 값을 저장한 후 진행
• arr[i]의 값이 dp[len]보다 작다면, 해당 값을 통해 만들 수 있는 길이를 탐색
  
  • 값이 클 때만 len이 늘어나면서 진행되기 때문에 dp는 정렬된 상태입니다.
  • arr[i]는 현재 탐색된 가장 마지막 값이므로, 앞에 탐색된 모든 더 작은 값들의 뒤에 위치할 수 있습니다.
  • 동시에 보다 큰 값 뒤로 가면 증가하는 수열이 아니므로, 그 앞에만 위치할 수 있습니다.
    • 시작값을 0, 끝 값을 len, arr[i]값을 탐색할 value으로 해서 dp배열을 이분 탐색 합니다.
    • arr[i]보다 큰 값들 중 가장 작은 값의 위치를 탐색한 뒤, 해당 위치의 값을 arr[i]로 갱신합니다.

 

이렇게 하면 갱신된 dp까지의 길이가 증가하는 부분 수열 길이의 최댓값이 됩니다.

 

글과 그림을 바탕으로 구성한 코드입니다.

package solution.classTest.class5;

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

public class test12015 {
    static int N;
    static int[] arr;

    // 길이 별 마지막 값의 최대값 저장
    static int[] dp;
    public static void main(String[] args) {
        init();

        int idx = 0;

        for (int i = 1; i < N; i++) {
            if (dp[idx] < arr[i]){
                idx++;
                dp[idx] = arr[i];
            }else {
                int l = 0;
                int r = idx;
                int mid;

                while(l<r){
                    mid = (l+r) / 2;

                    if (dp[mid] < arr[i]){
                        l = mid + 1;
                    }else {
                        r = mid;
                    }
                }

                dp[r] = arr[i];
            }
        }

        System.out.println(idx+1);
    }


    private static void init() {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            N = Integer.parseInt(br.readLine());

            arr = new int[N];
            dp = new int[N];

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            dp[0] = arr[0];

            br.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

 

 

저는 스택, 이분탐색, DP 이 세 가지 키워드에 유독 약한데

이번 문제도 풀이까지 올렸지만 풀면서 정말 고생을 많이 했습니다.

문제 분류에 이분탐색이 없었다면 접근도 못했을 문제였던 것 같습니다.

한마디로 실전이었다면.. 예... 끔찍하네요.

 

다른 풀이로는 세그먼트 트리를 이용한 방법이 있다고 합니다.

부분합, 부분곱 등 범위 데이터 처리에 유리한 방식이라고 하니 조만간 공부해 보렵니다.