[알고리즘] LIS 최장 증가 부분 수열, SegmentTree

최장 증가 부분 수열이란?

A라는 수열ㄹ에서 연속되는 것과 상관없이 Ai < Aj (단, i < j)를 만족하는 부분 수열입니다.

[10, 20, 10, 30, 20, 50]

위와 같이 수열이 주어졌을 때, 

[10, 20] [10, 20, 30] [10, 20, 30, 50] ... 모두 증가 부분 수열이며, 그 중 가장 길이가 긴 부분 수열이 최장 증가 부분 수열입니다.

 

 

어떻게 구하나?

동적계획법을 이용하여 구할 수 있습니다.

수열 A가 주어졌을 때, D(i)를 i번째 수를 부분 수열의 마지막으로하는 부분 수열 중 가장 길이가 긴 수열의 길이라고 한다면,

D(i)는 Ai보다 앞에 있고 Ai보다 작은 Aj의 j에 대하여 D(j)가 가장 큰 값 + 1이될 것입니다.

즉 index 0부터 차례로 순회하며 Di를 구하면 됩니다. 

수도 코드로 나타내면 다음과 같습니다.

Array[] A = 입력받은 수열

Array[] dp = A와 같은 사이즈로 선언

dp[0] = 1;

int lis //LIS 저장할 변수

for( i = A의 인덱스1부터 마지막까지) {

    int m // 최대 값을 담을 변수

    for( j = A의 인덱스0부터 i - 1까지) {

        if(A[j] < A[i]) {

            m = max(m, dp[j])

        }

    }

    dp[i] = m + 1

    lis = max(lis, dp[i)

}

위와 같은 방법으로 O(N^2)의 시간 복잡도로 LIS를 구할 수 있습니다.

 

비효율은 없나?

이 알고리즘의 실행시간을 단축시킬 수는 없을까요?

사실 D(i)는 Ai보다 앞에 있고 Ai보다 작은 Aj의 j에 대하여 D(j)가 가장 큰 값 + 1이지만,

위의 알고리즘에서는 모든 원소를 순회하면서 Ai보다 같거나 큰 값도 전부 검사하고 있습니다. 따라서, A를 오름차순으로 정렬하여 항상 Ai보다 작거나 같은 값에 대해서만 검사하도록 순서를 바꾼다면, 조금 더 효율적인 알고리즘이 될 것입니다. 

 

또한 SegmentTree를 활용할 수도 있습니다. SegmentTree는 구간에 대한 연산을 빠르게 하는 자료구조입니다. 구간 연산에 O(logN)의 시간 복잡도를 갖습니다. 기존 알고리즘에서 Ai보다 앞에 있고 Ai보다 작은 Aj의 j에 대하여 D(j)가 가장 큰 값을 구하기 위해서 모든 원소를 돌며 최대값을 찾는 O(N)의 시간 보다 단축할 수 있습니다. 

 

이 알고리즘에서 구간 연산을 N번 수행함으로 최종 시간 복잡도는 O(N log N)입니다.

 

오름차순 정렬과 SegmentTree를 적용하는 알고리즘은 다음과 같습니다.

 

1. Array A = 주어진 수열
2. D(i) = A[i]를 마지막 값으로하는 최장 부분 증가 수열의 길이
3. 위의 알고리즘을 점화식으로 표현하면, 
   D(i) = Max(D(j))(단, 0 <= j < i, A[i] < A[j])
4. 그런데 D(i)를 구할 때 A[i]보다 같거나 큰 A[j]는 아무런 관련이 없음.
5. 그래서 A[i] 값을 기준으로 오름차순 정렬해서, 작은 값부터 D[i]를 구해보자.
6. 그러면 모든 값에 대하여 A[i] < A[j]가 성립으로 점화식은 D(i) = Max(D(j))(단, 0 <= j < i)
7. segmentTree에 구간의 최대값을 같은 순서대로 기록한다.
   A[i]가 작은 값부터 계산이 되기 때문에, segmentTree에 기록된 값은 A[i]와 같거나 보다 작은 값들만 고려했을 때의 D(i)가 기록된다.
8. 또한 중복 값이 있을 경우, 기존 A의 인덱스를 기준으로 내림차순 정렬하여, 뒤에 오는 중복 값부터 계산하여 오산을 막는다.

예를 들어보겠습니다. 10 20 10 30 20 50 순서의 수열이 있습니다.
작은 값부터 계산하기 위해, 오름차순 정렬합니다.(같은 경우 인덱스 기준 내림차순 정렬)
sortedArr[value(index)] :  10(2) 10(0) 20(4) 20(1) 30(3) 50(5)
범위 검색을 최적화하기 위해 segmentTree를 사용합니다.
                      (  )
            (  )                 (  )
      (  )       (  )       (  )      (  )
   (  ) (  )  (  ) (  )  (  ) (  )  (  ) (  )
이때, segmentTree에 담긴 값은 sortedArr[i]까지 확인했을 때,  sorrtedArr[i]의 value 보다 작거나 같은 값에 한정하여 LIS를 계산한 값입니다.
segmentTree[i] = Max(segmentTree[i * 2 + 1], segmentTree[i * 2 + 2])이고,
tree의 리프 노드에 D(i)가 기록됩니다.

가장 작은 값 10(2)를 꺼내, A[0]~ A[1] 까지의 LIS를 계산하면 지금은 0입니다.
따라서 현재 D(2)의 값은 0 + 1이고, 이것을 segment tree에 저장합니다.
                      ( 1)
            ( 1)                 (  )
      (  )       ( 1)       (  )      (  )
   (  ) (  )  ( 1) (  )  (  ) (  )  (  ) (  )
그다음 값 10(0)을 꺼내, index가 0임으로 D(0) = 1입니다.
이렇게 인덱스 내림차순을 통해 계산 오류를 방지합니다.
                      ( 1)
            ( 1)                 (  )
      ( 1)       ( 1)       (  )      (  )
   ( 1) (  )  ( 1) (  )  (  ) (  )  (  ) (  )
그다음 값 20(4)를 꺼내, dp[0] ~ dp[3] 중 최대값을 찾습니다.
0~3 범위는 segmentTree[1]임으로 1이고, 따라서 dp[4] = 1 + 1 = 2입니다.
이를 트리에 기록합니다.
                      ( 2)
            ( 1)                 ( 2)
      ( 1)       ( 1)       ( 2)      (  )
   ( 1) (  )  ( 1) (  )  ( 2) (  )  (  ) (  )
이것을 반복한 후 tree의 rootNode가 최종 LIS가 됩니다.

 

java 코드는 아래와 같습니다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static public int numberOfLeaves;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            arr[i] = new int[]{Integer.parseInt(st.nextToken()), i}; // {value, index}
        }
        int[][] sortedArr = Arrays.copyOf(arr, arr.length);
        //value기준 오름차순, index기준 내림차순 정렬
        Arrays.sort(sortedArr, (a1, a2) -> a1[0] == a2[0] ? a2[1] - a1[1] : a1[0] - a2[0]);
        //segmentTree생성
        int[] segmentTree = initSegmentTree(N);
        // 정렬한 배열을 순차적으로 조회하며, dp[i] 갱신
        for(int i = 0; i < N; i++) {
            int value = sortedArr[i][0];
            int index = sortedArr[i][1];
            //arr[0] ~ arr[i - 1] 범위의 최대 LIS
            int maxBefore = findTheGreatest(index - 1, segmentTree);
            int maxCurrent = maxBefore + 1;
            //segmentTree에 저장하기
            updateTree(index, maxCurrent, segmentTree);
        }
        System.out.println(segmentTree[0]);
    }
   
    static int findTheGreatest(int findEnd, int[] segmentTree) {
        if(findEnd == -1) {
            return 0;
        }
        return findTheGreatest(0, numberOfLeaves - 1, 0, findEnd, 0, segmentTree);
    }
    static int findTheGreatest(int start, int end, int findStart, int findEnd, int index, int[] segmentTree) {
        if(findEnd < start || end < findStart) {
            return 0;
        }
        if(findStart <= start && end <= findEnd) {
            return segmentTree[index];
        }
        int mid = (start + end) / 2;
        return Math.max(findTheGreatest(start, mid, findStart, findEnd, index * 2 + 1, segmentTree),
                findTheGreatest(mid + 1, end, findStart, findEnd, index * 2 + 2, segmentTree));
    }
    static int updateTree(int index, int value, int[] segmentTree) {
        return updateTree(0, 0, numberOfLeaves - 1, index, value, segmentTree);
    }
    static int updateTree(int node, int start, int end, int index, int value, int[] segmentTree) {
        if(index < start || end < index) {
            return 0;
        }
        if(start == end) {
            return segmentTree[node] = value;
        }
        int mid = (start + end) / 2;
        int greaterOne = Math.max(updateTree(node * 2 + 1, start, mid, index, value, segmentTree),
                updateTree(node * 2 + 2, mid + 1, end, index, value, segmentTree));
        return segmentTree[node] = Math.max(segmentTree[node], greaterOne);
    }

    static int[] initSegmentTree(int numberOfValues) {
        int level = (int) Math.ceil(Math.log(numberOfValues) / Math.log(2));
        numberOfLeaves = (int) Math.pow(2, level);
        int lengthOfTree = calculateLength(level);
        return new int[lengthOfTree];
    }
    static int calculateLength(int levels) {
        int sum = 0;
        for(int i = 0; i <= levels; i++) {
            sum += Math.pow(2, i);
        }
        return sum;
    }
}