[알고리즘] 최장 증가 수열 - 이분 탐색 활용 : O(NlogN) Java

Concept

기존 dp 메모이제이션을 활용한 LIS에서 시간복잡도를 줄이기 위해 이분탐색을 활용

 

기존 LIS에서 앞쪽 수열을 보고 큰 값을 찾고 값을 갱신하는데 드는 시간인 O(N)을 줄일 수 없을까에서 비롯된 방식

 

사전지식으로 LowerBound 이분탐색에 대한 이해와 O(N^2)방식의 이해가 요구.

 

---

Feature

시간복잡도의 경우 모든 원소를 탐색하는 시간 O(N)에 대해 이분탐색 O(NlogN)을 수행함으로 총 O(N * NlogN)이므로 O(NlogN)의 시간으로 최장 증가 수열을 구할 수 있음.

 

---

Implement

1. 각각의 원소 i에 대해서 현재 기록된 lis배열의 끝 인덱스와 비교하여 i가 더 크다면 뒤에 추가

 

2. i가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐색하여 해당 자리의 값과 교체

핵심 코드

point = 0;

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

            if(lis[point] < arr[i]) {
                lis[++point] = arr[i];
            }
            else {
                int idx = lowerBound( 0, point, arr[i]);
                lis[idx] = arr[i];
            }

        }

 

---

위 코드의 동작과정을 간단하게 그림으로 나타내면

process 1

 

Process 2

 

Process 3

Process 4

 

Process 5

 

위와 같은 동작과정이 원소의 수(N)만큼 반복되며 해당 과정을 진행할 때 마다 lis배열의 값이 바뀌는 것을 보면

 

그림과 같이 값이 변경되는 것을 알 수 있다.

 

최종적으로 최장 증가 수열의 길이는 lis배열의 끝을 가리키는 point 변수의 값과 동일하게 됨.

---

전체 소스코드

import java.io.*;
import java.util.*;

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

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

        arr = new int[N];
        lis = new int[N+1];

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

        point = 0;

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

            if(lis[point] < arr[i]) {
                lis[++point] = arr[i];
            }
            else {
                int idx = lowerBound( 0, point, arr[i]);
                lis[idx] = arr[i];
            }

        }

        sb.append(point+1).append("\n");

        System.out.println(sb);
    }

    private static int lowerBound(int low, int high, int key) {
        while(low < high) {
            int mid = (low + high) / 2;

            if(lis[mid] < key) { //mid값보다 현재 key값이 크다면 오른쪽에서 탐색
                low = mid + 1;
            }
            else { //작을경우 왼쪾에서 탐색
                high = mid;
            }
        }
        return high;
    }
}

 

 

---

부분 수열 길이 구하기

아마 위의 동작과정을 보고나면 단순하게 lis배열의 원소를 순서대로 출력하면 되지 않을까라는 접근을 하게 될텐데, 최장 증가 수열의 원소를 구하기 위해서는 추가적으로 BackTrace(역추적)이 필요함.

 

만약 lis배열을 그대로 출력하게 될 경우 반례로

4
10 15 5 20

 

 

이처럼 입력이 들어올 경우 lis의 결과는 5, 15, 20이 되며, 최적해를 보장할 수 없다라는 것을 알 수 있다.

왜냐하면 이분탐색을 통해 구해진 자리에 값 교체가 이루어지는 것 자체가 현재 탐색된 수열길이 중에서 해당 수열이 들어갈 수 있는 자리를 탐색하는 것이기 때문임.

 

그래서 수열의 원소를 추가적으로 구하기 위해서는 BackTrace를 통해서 구해야함.

 

---

BackTrace Implement

역추적을 하는 방법으로는 우선 수열 후보를 담는 1차원 배열 v를 추가로 초기화

메인 로직에서 수열원소가 추가될 때마다 v배열에 추가되는 원소가 들어가는 인덱스 번호를 기록

 

각 인덱스 별 후보 수열 원소가 담겼다면 v배열의 끝에서부터 탐색 시작

끝에서부터 탐색하기 때문에 LIFO 특성을 가지는 스택을 사용하면 수열 결과를 오름차순으로 출력하기 편함.

 

v[i]와 수열의 길이를 나타내는 point 변수와 비교하여 같다면 해당 번호의 원소는 수열 후보가 될 수 있기 때문에 스택에 추가하고 point의 값을 1 감소 (수열의 길이와 같은 후보가 나와야하기 때문에 감소)

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_14003 가장 긴 증가하는 부분 수열 5
public class Main {
    static int N, point;
    static int INF = 1000000000;
    static int[] arr, lis;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuffer sb = new StringBuffer();

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

        arr = new int[N];
        lis = new int[N+1];
        Arrays.fill(lis, INF);

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

        point = 0;
        int[] v = new int[N+1]; //BackTrace를 위한 코드
        for(int i=0; i<N; i++) {

            if(lis[point] < arr[i]) {
                lis[++point] = arr[i];
                v[i] = point; //BackTrace를 위한 코드
            }
            else {
                int idx = lowerBound( 0, point, arr[i]);
                lis[idx] = arr[i];
                v[i] = idx; //BackTrace를 위한 코드
            }

        }

        sb.append(point+1).append("\n");

        //BackTrace Start
        Stack<Integer> stack = new Stack<>();
        for(int i= arr.length-1; i>=0; i--) {
            if(point == v[i]) {
                stack.push(arr[i]);
                point--;
            }
        }

        while(!stack.isEmpty()) sb.append(stack.pop() + " ");
        //BackTrace End

        System.out.println(sb);
    }

    private static int lowerBound(int low, int high, int key) {
        while(low < high) {
            int mid = (low + high) / 2;

            if(lis[mid] < key) { //mid값보다 현재 key값이 크다면 오른쪽에서 탐색
                low = mid + 1;
            }
            else { //작을경우 왼쪾에서 탐색
                high = mid;
            }
        }
        return high;
    }
}

 

---

정리

이분탐색을 활용한 LIS의 핵심은 각 원소를 기준으로 앞 부분을 완전 탐색하는 것을 lowerbound탐색으로 시간을 줄이는 것

수열의 원소를 출력해야할 경우에는 LIS배열을 채우는 과정에서 해당 수열이 들어갈 수 있는 자리에 대한 값을 추가적인 배열을 써서 기록해놓는 것으로 역추적을 할 수 있음.

역추적 과정은 최장 증가 수열 길이와 인덱스를 담은 배열의 값과 비교하는 것으로 진행됨

 

이번 정리를 하면서 LIS에 대한 로직은 이해가 갔지만 확실히 역추적에 대해서 이해하는데에는 시간이 오래걸림...

 

---

관련문제

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

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

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

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

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

2568번: 전깃줄 - 2

 

가장 긴 증가하는 부분 수열5와 전깃줄 - 2의 경우 수열의 원소를 출력해야하는 문제로 역추적 연습해보기 좋다고 생각함.