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

1. 가장 긴 증가하는 부분 수열, Logest Increasing Subsequence

 

증가부분수열이란, 주어진 수열의 일부 원소를 골라내서 만든 부분수열 중

 

모든 원소가 오름차순 부분 수열이다.

 

예를 들어 3 5 7 1 2 5 4 8 7 에서 3 5 7 8을 골라내면 이는 증가하는 부분 수열이다.

1 2 7, 2 5 역시 마찬가지

 

이 중 그 길이가 가장 긴 증가 부분 수열을 최장 증가 부분 수열, LIS라고 한다.

 

위의 예시에서는 3 5 7 8 또는 1 2 4 8 이 LIS가 될 수 있다.

 

 

 

2. DP와  LIS

 

LIS알고리즘 문제는 보통 주어진 수열에 대한 LIS의 길이를 구하는 것이다.

 

동적계획법, Dynamic Programming 알고리즘 문제의 예시로 쉽게 접할 수 있는 문제이므로 

 

DP를 공부 중이라면 꼭 짚고 넘어가야할 필요가 있다.

 

DP의 중요한 두가지는 1. 이전 값들을 기록할 배열 과 2. 배열을 이용해 다음 값을 유도할 점화식 임을 기억하고

 

두가지 DP 알고리즘을 살펴보자.

 

 

 

 

3. O(n^2) 알고리즘

 

단순하고 전형적인 DP알고리즘이다.

 

주어진 수열을 배열 s, 값을 저장할 배열을 dp라고 하고

 

dp[i] 를 i번째 원소를 마지막 값으로 가지는 LIS의 길이를 의미한다고 정의하자.

 

(편의를 위해 1번째부터 시작하고 dp[0] = 0 )

 

dp[i] = s[1]부터 s[i-1]  까지의 원소 중 s[i]보다 작은 원소 s[k]에 대해, dp[k] 중 가장 큰 값 + 1

 

쉽게 생각하면 현재 원소가 LIS를 이루는 원소가 되기 위해서는, 그 앞 원소들이 자신보다 작아야하기 때문이다.

 

 

#include<algorithm>

int LIS(int a[]){
    dp[0] = 0;
    dp[1] = 1;

    for(int i = 2; i <= N; i++){
        dp[i] = 0;
        for(int k = 1; k < i; k++){ 
            // 수열s를 1부터 i-1 까지 순회하면서 s[i]보다 작으면 그 dp[j] 중 가장 큰 값을 가져옴
            if(s[i] > s[k])
                dp[i] = max(dp[k], dp[i]);
        }
        dp[i]++;
    } 
    int res = *max_element(dp+1,dp+N+1); // dp중 최대값이 정답
    return res;
}

 

 

 

4. O(n log n) 알고리즘

 

O(n^2) 알고리즘의 오래걸린다. 왜 오래걸릴까

 

dp[i] 값을 구할 때 앞에서 부터 단순 탐색해서 오래걸린다..

 

탐색을 이진탐색으로 바꾸면 더 빠를 것 같다. 바꾸자

 

 

이 알고리즘은 L이라는 배열과 함께 진행한다.

 

L[i] = 길이가 i인 증가하는 부분수열을 만들 수 있는 마지막 원소 중 가장 작은 값

 

우리는 주어진 수열의 원소를 탐색해나가면서 현재 탐색 중인 원소가 LIS를 이루는 일부인지 알 수 없다.

 

 

위에서 정의한 L[i]의 의미를 잘 생각하며 원소를 하나씩 탐색해나가자

 

L을 채우는 법은 다음과 같다.

 

1) L이 empty 혹은 현재 탐색 중인 원소가 L의 마지막 원소보다 클 경우, L의 끝에 현재 원소를 추가한다. 

   L[i] 는 길이가 i 인 증가부분수열의 마지막 원소값이기 때문이다. 의미를 곱씹으면 쉽게 이해할 수 있다.

 

2) L의 마지막원소보다 작을 경우

   L 배열에서 현재 원소가 들어갈 수 있는 위치를 찾아 갱신(대체)한다.

   이때 들어갈 수 있는 위치를 찾을때 이진탐색을 이용한다.

 

 

예시를 보자

 

---

 

s : 3 5 7 2 1 4 8 7 

L :

---

 

s : 3 5 7 2 1 4 8 7 

L : 3

---

 

s : 3 5 7 2 1 4 8 7 

L : 3 5

---

s : 3 5 7 2 1 4 8 7 

L : 3 5 7

---

 

s : 3 5 7 2 1 4 8 7 

L : 2 5 7

 

 2가 들어갈 위치는 기존 3의 위치인 1번자리이다. 

L[i]는 길이가 i 인 증가부분수열의 마지막 원소값 중 가장 작은 값이기때문에,

원소 2까지 탐색한 시점에서 길이가 1인 부분수열의 마지막 원소가 될 수 있는 값 중 가장 작은 값은 3이 아닌 2이다.

---

 

s : 3 5 7 2 1 4 8 7 

L : 1 5 7

 

위와 똑같은 이유로 인해 이번에 탐색한 1이 기존 1번자리의 1을 대체하게 된다.

---

 

s : 3 5 7 2 1 4 8 7 

L : 1 4 7

---

 

s : 3 5 7 2 1 4 8 7 

L : 1 4 7 8

---

s : 3 5 7 2 1 4 8 7 

L : 1 4 7 8

 

 

끝까지 탐색했다면 L의 크기가 곧 우리가 찾는 LIS의 길이이다.

 

( ※ 주의 : L의 원소들은 LIS를 구성하는 원소들이 아니다. 우리는 길이에만 집중하자.)

 

 

이를 코드로 살펴보자

 

#include<vector>
using namespace std;

int N;
vector<int> L;

// L에서의 위치 찾아 반환
int binarySearch(int num, int left, int right){
    int mid;
    while(left < right){
        mid = (left + right) / 2;
        if(num > L[mid]) left = mid + 1;
        else right = mid;
    }
    return right;
}


// L의 길이는 구하고자하는 LIS의 길이와 같다
int LIS(int s[]){
    L.push_back(s[0]);

    int size = 0;

    // s를 탐색하며 L 채우는 과정
    for(int i = 1; i < N; i++){
        // L의 마지막원소가 더 작은 경우 L의 끝에 추가
        if (s[i] > L.back()){
            L.push_back(s[i]);
            size = L.size();
        } else{
        // L에서, 현재 탐색중인 원소가 들어갈 위치를 이진탐색 통해 찾음
            int pos = binarySearch(s[i], 0, size-1);
            L[pos]= s[i];
            size = L.size();
        }
    } 
    
    return L.size();
}​

(C++은 이진탐색으로 구현된 lower_bound() 함수를 쓰는게 편하지만 직관적인 이해를 위해 이진탐색함수를 구현하였다)

 

한번의 for 문과 이진탐색을 사용하므로

시간복잡도는 O(n log n) 이다.

 

이 알고리즘을 응용하여 LIS의 길이 뿐 아니라 LIS배열을 구할 수 있는데, 이는 나중에 다시 알아보도록하겠다.