LIS(최장 증가 부분 수열) 알고리즘

 

 

LIS - Longest Increasing Subsequence 

LIS는 '최장 증가 부분 수열'이란 뜻으로 어떠한 수열 내의 부분 수열들 중, 이전의 원소보다 다음 원소가 큰 원소들로만 이루어진 수열을 '증가 부분 수열' 이라고 하고, 이러한 증가 부분 수열들 중 가장 길이가 긴(원소의 개수가 많은) 수열을 최장 증가 부분 수열이라고 한다.

 

 

(참고 - LCS란?)

LCS는 Longest Common Subsequence 혹은 Longest Common Substring으로, S가 무엇을 뜻하냐에 따라 의미가 달라진다.

Longest Common Subsequence 는 최장 공통 부분수열,  Longest Common Substring는 최장 공통 문자열을 뜻하며, 

둘의 차이는 아래 그림을 보면 쉽게 이해할 수 있을 것이다.

https://chanhuiseok.github.io/posts/algo-49/

 

 

 

---

 

 

LIS의 알고리즘

LIS는 DP와 이분탐색 두 가지 방법으로 해결할 수 있다.

DP의 경우 구현은 비교적 간단하지만 시간복잡도가 O(n^2)이나 되기 때문에 주어지는 배열이 길다면 사용할 수 없다.

이분탐색으로 풀게 된다면 O(NlogN)이라는 시간 복잡도로 문제를 해결할 수 있다.

 

이제 DP와 이분탐색으로 LIS를 해결하는 방법을 알아보도록 하자.

 

 

 

---

 

 

1. DP를 사용한 LIS 풀이

 

원리는 생각보다 단순하다.

 

탐색하려는 위치(인덱스)에 대해서, 그 전까지의 위치를들 처음부터 차례대로 탐색하며 현재 값과 비교해서 더 크다면 갱신해주는 식으로 진행하면 된다. 사실 말로는 표현이 조금 힘들어서 코드를 통해 설명하겠다.

 

public static int lisByDp(List<Integer> arr){
    List<Integer> lisSize = new ArrayList<>();

    for (int i = 0; i < arr.size(); i++) {//0부터 수열의 끝까지 차례대로 진행한다.
        lisSize.add(1);//처음에는 자기 자신만 포함될 것이므로 크기는 1로 초기화한다.


        /**
         * 수열의 처음부터 현재 인덱스(i) 전까지 탐색을 진행하며
         */
        for(int j =0; j < i; j++){


            /**
             * 만약 수열의 현재 인덱스(i)번째 수가 그 이전 인덱스(j)의 수보다 크다면
             * (ex: arr.get(j)는 2이고, arr.get(i)는 4인 그런 상황)
             */
            if(arr.get(j) < arr.get(i)){

                /**
                 * 현재 저장된 최장 부분수열의 길이와
                 * j 인덱스의 최장 부분수열에 값에 1을 더한 길이를 비교하며
                 * 더 큰 값을 현재 인덱스(i)의 최장 부분수열로 저장한다.
                 */
                lisSize.set(i, Math.max(lisSize.get(i), lisSize.get(j)+1));
            }
        }
    }


    /**
     * lisSize(인덱스별 최장 부분수열의 길이를 저장한 List) 의 최댓값을 구해서 반환
     */
    return lisSize.stream().max(Integer::compareTo).get();
}

 

 

 

 

---

 

2. 이분탐색을 사용한 LIS 풀이

사실 이분탐색을 이용한 LIS 알고리즘을 공부할 때, 인지부조화가 조금 심하게 와서 너무 헷갈리고 어려웠다..ㅎㅎ

별로 어려운건 아닌데 말이다.. 

 

주어진 배열의 처음 위치부터 시작하며 각 값들을 임의의 리스트 속에 이분탐색을 통해 정렬되게 집어넣는다.

단 기존의 배열 중간에 값을 추가해야 할 때는, 기존에 존재하는 값과 바꿔주어야 한다.

아래 예시를 보자.

 

 

주어진 배열이 [5, 6, 7, 1, 2, 5, 4]라고 하자. 여기서 이분 탐색을 통해 LIS를 구하는 방법은 다음과 같다.

먼저 빈 배열을 하나 만들자. 해당 배열을 dp[]라고 하겠다.

 

 

1. 인덱스: 0,    값: 5,    dp의 상태: []

이분탐색 진행 -> dp의 상태: [5]

 

2. 인덱스: 1,    값 6,    dp의 상태: [5]

이분탐색 진행 -> dp의 상태: [5, 6]

 

3. 인덱스: 2,    값 7,    dp의 상태: [5, 6]

이분탐색 진행 -> dp의 상태: [5, 6, 7]

 

4. 인덱스: 3,    값: 1,    dp의 상태: [5, 6, 7]

이분탐색 진행 -> dp의 상태: [1, 6, 7]

(값을 중간에 추가할 경우 기존 값을 버리고 대입)

 

5. 인덱스: 4,    값 2,    dp의 상태: [1, 6, 7]

이분탐색 진행 -> dp의 상태: [1, 2, 7]

 

6. 인덱스: 5,    값 5,    dp의 상태: [1, 2, 7]

이분탐색 진행 -> dp의 상태: [1, 2, 5]

(중복된 값은 따로 추가하지 않음)

 

7. 인덱스: 6,    값 4,    dp의 상태: [1, 2, 5]

이분탐색 진행 -> dp의 상태: [1, 2, 4]

 

 

다음 결과에서 dp의 길이는 총 3이므로, LIS는 3가 된다.

 

이제 코드로 살펴보자.

public static int lisByBiSearch(List<Integer> arr){//arr은 기준 수열
    List<Integer> lisInt = new ArrayList<>();//증가하는 부분 수열을 넣어줄 List

    lisInt.add(arr.get(0));//첫번째 수를 넣어둔다

    for (int i = 1; i < arr.size(); i++) {

        if(arr.get(i) > lisInt.get(lisInt.size()-1)){
        //만약 맨 뒤의 수보다 더 큰 수라면 따로 이분탐색을 진행하지 않고 마지막 위치에 추가
            lisInt.add(arr.get(i));
        }
        else {
            binarySearch(lisInt, arr.get(i));
        }

    }

    return lisInt.size();
}


public static void binarySearch(List<Integer> lisInt, int target){

    //탐색 범위는 처음부터 lisInt(증가하는 부분수열을 담아둔 배열)의 끝까지
    int start = 0;
    int end = lisInt.size()-1;

    while (start <= end){
        int mid = start + ((end - start) >>> 1); //나누기 2


        if(lisInt.get(mid) == target){
            return;
        }
        
        if(lisInt.get(mid) > target){//중간값이 더 크다? -> 범위를 더 작게
            end = mid-1;
        }
        
        if(lisInt.get(mid) < target){//중간값이 더 작다? -> 범위를 더 크게
            start = mid+1;
        }
    }
    lisInt.set(start, target);
}

 

 

 

 

 

 

 

 

Reference

 

https://loosie.tistory.com/376

[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)