최대 증가 부분 수열

최대 증가 부분 수열(LIS)이 뭘까요?

 

 

최대 증가 부분 수열(Longest Increasing Sequence)은 오름 차순으로 증가하는 부분 수열 중 가장 긴 부분 수열을 의미합니다.

하나의 예시를 통해서 알아보겠습니다.

10 20 30 10 40 50

 

오름 차순으로 증가 하는 부분 수열 중 가장 긴 부분 수열은 어떻게 될까요?

 

10 20 30 20 40 50

 

[10,20,30,40,50]이 됩니다.

 

중간에 20이 있는데 오름 차순으로 증가하는 부분 수열이 아니지 않나요?

10 20 30 20 40 50

 

[10,20]도 오름 차순으로 증가하는 부분 수열입니다.

 

어떤 부분 수열 배열이 최대 증가 부분 수열일까요?

 

[10,20,30,40,50]은 길이가 5인 부분 수열이고, [10,20]은 길이가 2인 부분 수열이고, 다른 부분 수열 배열도 5인 부분 수열보다 크지 않으므로 길이가 5인 [10,20,30,40,50]이 최대 증가 부분 수열입니다.

 

 

최대 증가 부분 수열 찾는 방법

 

 

 

1차원 배열을 0번 인덱스부터 순차적으로 탐색합니다.
이 과정에서 증가하는 부분 수열의 개수를 카운팅하면서 진행합니다.

먼저, 10은 배열의 첫 번째 값이므로, 증가하는 부분 수열의 길이는 자기 자신만 포함하는 1이 됩니다.

 

1번 인덱스로 값은 20이 됩니다. 앞 원소인 10이 20보다 작기 때문에, 증가하는 부분수열의 갯수는 이전 10과 자기 자신인 20으로 총 2개가 됩니다.

 

2번 인덱스의 값은 30입니다. 앞에 나온 값들 중 10과 20은 모두 30보다 작지만, 특히 20은 이미 길이 2인 가장 긴 증가 부분 수열을 이루고 있습니다. 따라서 20에 30을 이어 붙이면 길이가 3인 증가 부분 수열이 됩니다.

 

 

3번 인덱스의 값은 20입니다. 앞선 인덱스에서 20보다 작은 값은 10뿐이므로, 10에 20을 이어 붙여 길이 2의 증가 부분 수열을 만들 수 있습니다.

 

4번 인덱스의 값은 40입니다. 앞에 나온 값들 중 10, 20, 30은 모두 40보다 작지만, 그 중 30이 길이가 3인 가장 긴 증가 부분 수열을 이루고 있습니다. 따라서 30에 40을 이어 붙이면 길이가 4인 증가 부분 수열이 됩니다.

 

5번 인덱스의 값은 50입니다. 앞에 나온 값들 중 10, 20, 30, 40은 모두 50보다 작지만, 그 중 40이 길이가 4인 가장 긴 부분 수열을 이루고 있습니다. 따라서 40에 50을 이어 붙이면 길이거 5인 증가 부분 수열이 됩니다.

 

 

최종적으로 가장 긴 증가 부분 수열은 [10, 20, 30, 40, 50]으로 길이가 5인 배열이 됩니다.

 

코드로 어떻게 구현할까요?

 

코드 구현 (O(n²))

이중 for 문을 사용하여, 각 인덱스에서 앞선 인덱스들의 정보를 활용해 최대 증가 부분 수열(LIS)의 길이를 갱신하는 방식입니다.

(단, 아래 코드는 최대 증가 부분 수열의 길이만 알아내는 로직이므로, 위에 명시된 최대 증가 부분 수열을 찾는 방법이랑 로직상 일치하지 않습니다.)

public class LIS {
    public static void main(String[] args) {
        int[] arr = {10,20,30,20,40,50};
        int[] cnt = new int[arr.length];

        int lis = 0;

        for(int i = 0; i < arr.length; i++) { // 배열 index 하나씩 순차 탐색
            int maxValue = 0; // 제일 긴 부분수열 길이 누적
            for(int j = 0; j < i; j++) { // 이전 index ~ 현재 index 이전 까지 탐색
                if(arr[j] < arr[i] && maxValue < cnt[j]) { // 크기 비교 및 증가하는 부분 수열 갯수 비교
                    maxValue = cnt[j];
                }
            }
            cnt[i] = maxValue + 1;
            lis = Math.max(lis,cnt[i]);
        }

        System.out.printf("최대 증가 부분 수열 길이 : %d", lis);
    }
}

 

출력 결과는 아래와 같습니다.

 

 

시간 복잡도는 어떻게 될까요?

 

이중 for 문을 사용하기 때문에 시간 복잡도는 O(n²)이 됩니다.

 

 

만약 증가하는 부분 수열의 원소를 출력하고 싶은 경우엔 어떻게 할까요?

 

추적하는 방법을 사용합니다.

추적하는 원리는 아래의 이미지와 같습니다.

• 5번 인덱스는 4번 인덱스를 가리킵니다.
• 4번 인덱스는 3번 인덱스를 가리킵니다.
• 3번 인덱스는 2번 인덱스를 가리킵니다.
• 2번 인덱스는 1번 인덱스를 가리킵니다.

이런 식으로 이전 인덱스에 대해 추적을 하면, 최대 증가 부분 수열의 원소도 알아낼 수 있습니다.

 

 

코드로 어떻게 구현할까요?

 

코드 구현

public class LIS {

    private static int[] arr;
    private static int[] cnt;
    private static int[] trace;

    public static void main(String[] args) {
        arr = new int[]{10,20,30,20,40,50};
        cnt = new int[arr.length];

        int lis = 0;
        trace = new int[arr.length];
        Arrays.fill(trace, -1);
        int idx = 0;
        for(int i = 0; i < arr.length; i++) { // 배열 값
            for(int j = 0; j < i; j++) { // 이전 값
                if(arr[j] < arr[i] && cnt[i] < cnt[j] + 1) { // 크기 비교 및 증가 부분 수열 갯수 비교
                    cnt[i] = cnt[j] + 1;
                    trace[i] = j;

                    if(lis < cnt[i]) {
                        lis = cnt[i];
                        idx = i;
                    }
                }
            }
        }

        List<Integer> lisNumber = new ArrayList<>();
        printLIS(idx, lisNumber);

        System.out.println("최장 증가 부분 수열 : " + lisNumber.reversed());
    }

    private static void printLIS(int index, List<Integer> lisNumber) {
        if(index == -1) return;
        lisNumber.add(arr[index]);
        printLIS(trace[index], lisNumber);
    }
}

 

 

출력 결과는 아래와 같습니다.

 

시간 복잡도는 어떻게 될까요?

 

이중 for 문을 사용하기 때문에 시간 복잡도는 O(n²)이 됩니다.

 

시간 복잡도가 너무 크게 나오는데 줄일 수 있는 방법은 없나요?

 

최대 증가 부분 수열 (O(NlogN))

NlogN의 방법으로 구현할 수 있습니다.

흐름은 아래와 같습니다.

 

순차적으로 일차원 배열을 탐색합니다. 현재 그림 하단에 놓여있는 빈 배열엔 아무 값도 존재하지 않으므로, 10을 추가해 줍니다.

 

이전과 같은 방식으로 배열에 20을 추가해줍니다.

이전과 같은 방식으로 배열에 30을 추가했습니다. 

 

현재 누적된 배열의 값중 20이 존재하기 때문에, 배열에 추가하지 않습니다.

만약 20이 아닌 25인 경우엔 20과 30 사이에 값을 추가해 줍니다.

 

이전과 같은 방식으로 40을 추가해줍니다.

 

최종적으로 50을 추가해줍니다.

 

 

코드로 어떻게 구현할까요?

 

이분탐색을 사용해서 배열에 넣을 원소의 위치를 찾아줍니다. 코드는 아래와 같습니다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {

        int[] arr = new int[]{10,20,30,20,40,50};

        List<Integer> lis = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            if (lis.isEmpty() || lis.get(lis.size() - 1) < num) {
                lis.add(num);
            } else {
                int left = 0;
                int right = lis.size();

                while (left < right) {
                    int mid = (left + right) / 2;

                    if (lis.get(mid) < num) { // 더 작은 경우
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }

                lis.set(left, num); // 부분 증가 수열 갱신
            }
        }

        System.out.println(lis);
    }
}

 

출력 결과

 

시간 복잡도는 어떻게 될까요?

 

배열 선형 탐색 N에 이분 탐색(logN)이 곱해지기 때문에 O(NlogN)이 됩니다.

 

정리

• 최대 증가 부분 수열(Longest Increasing Sequence)은 오름 차순으로 증가하는 부분 수열 중 가장 긴 부분 수열을 의미합니다.
• O(NlogN)의 시간복잡도로 구현할 수 있습니다.