[도구정리] 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

용어 정리

 

수열 : 연속된 수의 나열

증가 : 값이 꾸준히 증가함

최장 : 최대의 길이

 

너무나도 당연한 소리일 수도 있지만 연속된! 수열이 아니라는 것을 설명하기 위해 한 소리이다.

수열을 접하다 보면 습관적으로 연속된 수열이 몸에 익은데 이 문제는 그게 아니라는 말이다.

 

예를 들어,

1

3

2

5

위와 같은 수열에서  연속된 최장 증가수열은 1 3 혹은 2 5로 길이가 2일 수 있으나,

1

3

2

5

LIS의 경우 1 2 5로 3의 길이를 갖는다는 것이다.

---

구현

 

대표적인 문제로는

백준 11053 https://www.acmicpc.net/problem/11053

소프티어 징검다리 https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제를 들 수 있다.

 

대표적인 구현으로는

1. DP(O(N^2))

2. DP + 이분탐색(O(NlogN))이 있다.

 

이 중 시간복잡도가 더 좋은 이분탐색을 응용한 코드를 살펴보자.

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

public class Main {
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine()); // 돌의 개수

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

        int firstHeight = Integer.parseInt(st.nextToken()); // 0번째 돌의 높이
        list.add(firstHeight); // 0번째 돌의 높이 리스트에 추가

        for(int i = 1; i < n; i++){ // 1번째 돌부터
            int height = Integer.parseInt(st.nextToken());
            if(height > list.get(list.size() - 1)){ // 만약 돌의 높이가 현재까지 중 최고라면
                list.add(height); // 리스트에 그냥 추가
                continue;
            }
            int idx = binarySearch(height); // 돌의 높이를 대체할 인덱스 찾기
            list.set(idx, height); // 리스트에 값 변경
        }

        System.out.println(list.size()); // 리스트 사이즈가 밟을 수 있는 돌의 최대 갯수
    }

    public static int binarySearch(int num){
        // 1 2 4 가 있는데 3이 들어옴
        int start = 0; // 0
        int end = list.size()-1; // 2
        int mid = (start + end) / 2; // 1
        while(start <= end){
            mid = (start + end) / 2;
            if(list.get(mid) == num){ // 처음에 mid == 1이기 때문에 3이 아님 (list.get(mid) == 2)
                return mid;
            }
            if(list.get(mid) < num){ // 처음에 mid == 1이기 때문에 3보다 작음 (list.get(mid) == 2)
                start = mid + 1; // start = 1 + 1이므로 2이가 됨.
                continue;
            }
            end = mid - 1; // start = 2가 되었을 때 mid = 2가 되고, list.get(mid) == 4이므로 여기로 내려옴.
            // end = 2 - 1이 되어 반복문 끝남.
        }
        return start; // 2가 반환됨
    }
}

 

해당 코드는 소프티어 문제에 대한 풀이이다.

이를 통해 코드를 알아보자. 만약 이분탐색에 대해 잘 모른다면 https://to-travel-coding.tistory.com/305 참고하자.

 

규칙은 다음과 같다.

1. 첫번째 수열의 값을 리스트에 추가한다.

2. 다음 입력값이 리스트의 끝(코드를 보다 보면 알겠지만 리스트는 자연스럽게 오름차순 정렬이 된다.) 보다 크다면 리스트에 추가한다.

3. 입력값이 리스트의 끝보다 작다면 어떠한 인덱스의 값을 바꿔줄 것인지 이분탐색을 통해 찾는다.

4. 이분탐색을 통해 찾은 인덱스의 값을 대체한다.

 

예를 들어,

1

2

4

3

5

라는 수열이 있다고 하자.

 

1

1. List<Integer>의 시작은 [1] 일 것이다. (List <Integer>의 상태 : [1])

1

2

2. 2가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List <Integer>의 상태 : [1, 2])

1

2

4

3. 4가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List <Integer>의 상태 : [1, 2, 4])

1

2

3

4. 3이 들어온다. 3번 규칙에 의해 이분탐색을 통해 인덱스 2를 대체해야 함을 알게 된다. 인덱스 2에 있는 4를 값 3으로 바꿔준다.

(List의 상태 : [1, 2, 3])

-> 이분탐색이 이해가 안 된다면 코드의 주석을 참고하자.

1

2

3

5

5. 5가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List<Integer>의 상태 : [1, 2, 3, 5])

 

최종적으로, LIS인 1 2 3 5가 완성되며 길이는 list.size()가 된다.