알고리즘의 기본적인 스킬을 다룹니다.

이번 포스트에서는 알고리즘의 스킬 중 LIS(최장 증가 수열)에 대해서 알아 보려고 합니다.
목차는 다음과 같습니다.

1. 최장 증가 수열이란?
2. 최장 증가 수열의 경로는?
3. 이진탐색을 통해 최장 증가 수열 찾기
4. 이진탐색을 통해 최장 증가 수열의 경로는?

LIS

LIS란 Longest Increasing Subsequence 최장 증가 수열이라고 말하며, 이는 어떤 수열이 나열 되어있을때, 그 배열의 순서를 유지하며 크기가 점차 커지는 가장 긴 부분수열의 길이가 몇인지를 구하는 알고리즘이라고 할 수 있습니다.

무슨 말인지 예를 들어서 한번 보도록 하겠습니다.

3, 2, 6, 4, 5, 1
위와 같은 수열이 있다고 가정하겠습니다.

이때 최장 증가 수열은 무엇일까요? 왼쪽에서 오른쪽으로 확인해보며 봤을 경우,
3, 4, 5 또는 2, 4, 5 가 점차적으로 증가하며 부분 수열인 것을 확인 할 수 있습니다.

그럼 이 부분 수열을 과연 어떻게 구할 수 있을까요? 한번 코드로 확인해보도록 하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Arrays;

public class LIS_DP {
    public static void main(String[] args) {
        int[] list = {3, 2, 6, 4, 5, 1};
        int[] LIS = new int[list.length]; // i 번째 숫자를 마지막 숫자로 사용할 경우 최장 증가 수열의 길이를 저장할 배열

        for (int i = 0; i < LIS.length; i++) {
            LIS[i] = 1;
            for (int j = 0; j < i; j++) {
                if (list[j] < list[i] && LIS[i] < LIS[j] + 1){
                    LIS[i] = LIS[j] + 1;
                }
            }
        }

        System.out.println(Arrays.toString(LIS));

        // 최대 값을 찾기
        int maxLISIndex = 0;
        for (int i = 0; i < LIS.length; i++) {
            if(LIS[maxLISIndex] < LIS[i]){
                maxLISIndex = i;
            }
        }
        System.out.println("최장 증가 수열의 길이 : " + LIS[maxLISIndex]);
    }
}

핵심코드는 이 부분 입니다.

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < LIS.length; i++) {
    LIS[i] = 1; // 모든 배열을 값을 1로 초기화
    for (int j = 0; j < i; j++) { // 내 앞의 숫자 중에 작은 숫자들을 찾기
        if (list[j] < list[i] && LIS[i] < LIS[j] + 1){
            // 나를 기준으로 내앞의 원소가 작으며,
            // 내가 들고있는 최장 증가 수열의 길이보다 그 값(+1)을 넣은 값이 크다면
            LIS[i] = LIS[j] + 1;
        }
    }
}

이 코드를 해석하자면 다음과 같이 나타 낼 수 있습니다.

주어진 수열
{ 3, 2, 6, 4, 5 ,1 }

LIS(1) LIS(2) LIS(3) LIS(4) LIS(5) LIS(6)
1 1 2 2 3 1
{3} {2} {3, 6} {3, 4} {3, 4, 5} {1}
{3} {2} {2, 6} {2, 4} {2, 4, 5} {1}

따라서 최장 증가 수열의 제일 긴 길이는 LIS(5)의 3이라고 볼 수 있습니다.


경로 구하기

그렇다면 그 최장 증가 수열에서의 경로는 어떻게 구할까요?

코드를 한번 보도록 하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Arrays;

public class LIS_DP_Path {
    public static void main(String[] args) {
        int[] list = {3, 2, 6, 4, 5, 1};
        int[] LIS = new int[list.length]; // i 번째 숫자를 마지막 숫자로 사용할 경우 최장 증가 수열의 길이를 저장할 배열
        int[] path = new int[list.length]; // 경로를 역추적 할 배열

        for (int i = 0; i < LIS.length; i++) {
            LIS[i] = 1; // 모든 배열을 값을 1로 초기화
            path[i] = -1; // 내 앞의 수열 숫자의 index
            for (int j = 0; j < i; j++) { // 내 앞의 숫자 중에 작은 숫자들을 찾기
                if (list[j] < list[i] && LIS[i] < LIS[j] + 1) {
                    // 나를 기준으로 내앞의 원소가 작으며,
                    // 내가 들고있는 최장 증가 수열의 길이보다 그 값(+1)을 넣은 값이 크다면
                    LIS[i] = LIS[j] + 1;
                    path[i] = j; // 내 앞 수열을 찾았기 때문에 그 index 저장
                }
            }
        }

        System.out.println("LIS : " + Arrays.toString(LIS));

        // 최대 값을 찾기
        int maxLISIndex = 0;
        for (int i = 0; i < LIS.length; i++) {
            if (LIS[maxLISIndex] < LIS[i]) {
                maxLISIndex = i;
            }
        }
        System.out.println("최장 증가 수열의 길이 : " + LIS[maxLISIndex]);

        System.out.println("Path : " + Arrays.toString(path));
        StringBuilder lisPath = new StringBuilder();
        for (int i = maxLISIndex; i != -1; i = path[i]) {
            // 최장 증가 수열의 index번호를 기준으로 앞으로 이동하며 -1을 만날 때 까지 출력
            lisPath.insert(0, list[i] + " "); // 제일 처음으로 삽입
        }
        System.out.println(lisPath.toString());
    }
}

이 코드의 기본 원리는 내 앞의 수열 Index를 저장하며 마지막에 역추적한다.에 의미를 두고 있습니다.

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < LIS.length; i++) {
    ...
    path[i] = -1; // 내 앞의 수열 숫자의 index
    for (int j = 0; j < i; j++) { // 내 앞의 숫자 중에 작은 숫자들을 찾기
        if (list[j] < list[i] && LIS[i] < LIS[j] + 1) {
            ...
            path[i] = j; // 내 앞 수열을 찾았기 때문에 그 index 저장
        }
    }
}

내 앞의 숫자를 탐색하며 작은 숫자를 찾을 때 조금의 코드를 추가해주면서 작성할 수 있습니다.
path[i] = j;를 작성해주며 경로를 작성 할 수 있으며,
결과값을 보도록 하겠습니다.

1
2
3
4
LIS : [1, 1, 2, 2, 3, 1]
최장 증가 수열의 길이 : 3
Path : [-1, -1, 0, 0, 3, -1]
3 4 5

3, 4, 5가 나왔지만, 2, 4, 5 도 됩니다. 프로그램 상 앞으로 현재값을 기준으로 찾기 때문입니다.



좋습니다. 이렇게 최장 증가 수열에 대해서 알아봤지만, 이 알고리즘의 경우 O(n^2)의 시간 복잡도를 갖고 있습니다.

i를 n번 돌리며 j가 0부터 i까지 확인 하기 때문에.

좀 더 씬빡 한방법을 생각해보도록 하겠습니다.



Binary Search를 통해 LIS 찾기

Binary Search로 LIS를 어떻게 찾는지 예시를 통해 확인해보도록 하겠습니다.

8, 2, 4, 3, 6, 11, 7, 10, 14, 5 라는 수열이 있다고 가정해 보겠습니다.

LIS List는 LIS로 사용가능한 숫자를 저장하는 List라고 하겠으며,
LIS[i]는 가장 작은 값을 LIS[i]에 저장한다고 하겠습니다.

8 2 4 3 6 11 7 10 14 5
8 2 2 2 2 2 2 2 2 2
4 3 3 3 3 3 3 3
6 6 6 6 6 5
11 7 7 7 7
10 10 10
14 14

진행 순서는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
1 : 8을 LIS에 넣음
2 : 2를 LIS 이진 탐색을 통해 넣을 위치를 확인(2보다 작은 값 찾지 못함) -> -1을 리턴하며 0번째에 입력
3 : 4를 LIS 이진 탐색을 통해 넣을 위치를 확인(4보다 작은 값 2 위치를 -부호로) -> -2를 리턴하며 1번째에 입력
4 : 3를 LIS 이진 탐색을 통해 넣을 위치를 확인(3보다 작은 값 2 위치를 -부호로) -> -2를 리턴하며 1번째에 입력
4 : 6를 LIS 이진 탐색을 통해 넣을 위치를 확인(6보다 작은 값 3 위치를 -부호로) -> -3를 리턴하며 2번째에 입력
5 : 11를 LIS 이진 탐색을 통해 넣을 위치를 확인(11보다 작은 값 6 위치를 -부호로) -> -4를 리턴하며 3번째에 입력
6 : 7를 LIS 이진 탐색을 통해 넣을 위치를 확인(7보다 작은 값 6 위치를 -부호로) -> -4를 리턴하며 3번째에 입력
7 : 10를 LIS 이진 탐색을 통해 넣을 위치를 확인(10보다 작은 값 7 위치를 -부호로) -> -5를 리턴하며 4번째에 입력
8 : 14를 LIS 이진 탐색을 통해 넣을 위치를 확인(14보다 작은 값 10 위치를 -부호로) -> -6를 리턴하며 5번째에 입력
9 : 5를 LIS 이진 탐색을 통해 넣을 위치를 확인(5보다 작은 값 3 위치를 -부호로) -> -3를 리턴하며 2번째에 입력

이렇게 최장 증가 수열을 구할 수 있게 됩니다. 그럼 코드로 한번 작성해 보도록 하겠습니다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;

public class LIS_Binary {
    public static void main(String[] args) {
        int[] list = {8, 2, 4, 3, 6, 11, 7, 10, 14, 5};
        int[] LIS = new int[list.length]; // LIS로 사용가능한 숫자를 저장
        int size = 0; // LIS의 개수를 관리할 변수
        LIS[size++] = list[0]; // 첫번째 숫자는 바로 반영
        for (int i = 1; i < list.length; i++) {
            if(LIS[size-1] < list[i]){
                LIS[size++] = list[i]; // 제일 뒤에 붙이기
            }else{
                int temp = Arrays.binarySearch(LIS,0, size, list[i]); // 삽입할 위치
                if(temp < 0) temp = -temp -1;
                LIS[temp] = list[i];
            }
        }

        System.out.println("LIS : " + Arrays.toString(LIS));
        System.out.println("LIS의 개수 : " + size);
    }
}

이 코드에서 가장 중요한 부분은 이 부분 입니다. 

1
2
3
if(LIS[size-1] < list[i]){
    LIS[size++] = list[i]; // 제일 뒤에 붙이기
}

제일 뒤의 원소를 확인 했을 때, 넣을 원소보다 작은 경우에는 LIS 제일 뒤에 붙여넣습니다.

1
2
3
4
5
else{
    int temp = Arrays.binarySearch(LIS,0, size, list[i]); // 삽입할 위치
    if(temp < 0) temp = -temp -1;
    LIS[temp] = list[i];
}

그렇지 않을 경우 넣을 원소를 LIS 리스트에서 찾아 확인 후 -인덱스를 주며 넣을 위치에다 바꿔치기를 합니다.

결과를 보면 아래와 같습니다.

1
2
LIS : [2, 3, 5, 7, 10, 14, 0, 0, 0, 0]
LIS의 개수 : 6



경로 구하기 이진탐색

먼저 코드로 확인해보도록 하겠습니다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Arrays;

public class LIS_Binary_Path {
    public static void main(String[] args) {
        int[] list = {8, 2, 4, 3, 6, 11, 7, 10, 14, 5};
        int[] LIS = new int[list.length]; // LIS로 사용가능한 숫자를 저장, index 저장
        int[] path = new int[list.length]; // 경로를 역추적하기 위해
        int size = 0; // LIS의 개수를 관리할 변수

        path[size] = -1; // 첫번째 들어갈 수 이므로 -1을 저장
        LIS[size++] = 0; // 첫번째 숫자의 index를 반영

        for (int i = 1; i < list.length; i++) {
            // LIS 배열의 마지막 숫자와 수열값을 비교
            if (list[LIS[size - 1]] < list[i]) {
                path[i] = LIS[size - 1]; // 해당 위치를 path[i]에 넣음
                LIS[size++] = i; // 제일 뒤에 index 를 붙임
            } else {
                int temp = binarySearch(list, LIS, 0, size, list[i]); // 넣을 위치를 확인
                if (temp < 0) temp = -temp - 1;
                path[i] = path[LIS[temp]]; // 덮어쓸 위치의 index를 내것으로 복사
                LIS[temp] = i;
            }
        }
        System.out.println("LIS의 개수 : " + size);
        StringBuilder lisPath = new StringBuilder();
        for (int i = LIS[size - 1]; i != -1; i = path[i]) {
            lisPath.insert(0, list[i] + " ");
        }
        System.out.println("LIS의 경로 : " + lisPath.toString());
    }

    private static int binarySearch(int[] a, int[] c, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = low + high >>> 1;
            int midVal = a[c[mid]];
            if (midVal < key) {
                low = mid + 1;
            } else {
                if (midVal <= key) {
                    return mid;
                }
                high = mid - 1;
            }
        }

        return -(low + 1);
    }
}

위 코드가 좀 복잡해 보일 수 있는데, Binary Search 함수를 따로 구현한 이유는 LIS 리스트는 입력받은 list 배열의 Index를 저장했기 때문입니다.

path라는 리스트를 초기 인덱스(-1)부터 값을 LIS에 넣을 때마다 path를 추가해주는 방식을 사용했습니다.

그 경로를 -1이 나올때까지 결과는 다음과 같습니다.

1
2
LIS의 개수 : 6
LIS의 경로 : 2 3 6 7 10 14



이렇게 LIS(최장 증가 수열)에 대해서 알아 보았습니다.
그럼 관련 알고리즘 문제 링크를 걸어드리며 마무리 짓도록 하겠습니다. 감사합니다.😁

관련 알고리즘 문제

  가장 긴 증가하는 부분 수열

  전깃줄

  전깃줄2