Seungkwan's Lab.

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

알고리즘

어떠한 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)를 찾는 문제는 꽤나 유명한 문제입니다. 다이나믹 프로그래밍을 공부할 때 예시로 자주 나오는 문제이고, 프로그래밍 대회에도 종종 출제됩니다. 비교적 쉬운 O(N^2) 알고리즘과 좀 더 어렵지만 효율적인 O(N log N) 알고리즘이 있습니다. 두 알고리즘을 소개하겠습니다. 또한 이 글에서 배열의 인덱스는 편의상 0이 아닌 1부터 시작하는걸로 하겠습니다.


3

2  

5 

2  

3 

1  

4 

부분 수열

어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 그 수열의 부분 수열이라 합니다. 가령 위의 수열에서 부분 수열은 [3], [5], [2,5], [3, 5, 3, 1], [2, 3, 4] 등이 있습니다.. 물론 이 수열 자체도 자기 자신의 부분 수열입니다.


증가하는 부분 수열

어떠한 수열의 부분 수열들 중 오름차순인 것들을 증가하는 부분 수열이라 합니다. 가령 위의 수열에서 증가하는 부분 수열은 [2, 5] , [3, 4] , [2, 3, 4] 등이 있습니다. 이 글의 주제인 가장 긴 증가하는 부분 수열은 증가하는 부분 수열들 중 길이가 가장 긴 것을 의미합니다. 이름이 너무 기니까 편의상 LIS라고 부르겠습니다. 이 수열에서는 [2, 3, 4] 가 LIS가 됩니다.

O(N^2) 알고리즘

O(N^2) 알고리즘은 사실 다이나믹 프로그래밍을 공부한 사람은 어렵지 않게 생각할 수 있을만큼 쉽습니다. 다음과 같은 점화식으로 N^2시간에 구할 수 있습니다.

dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이

dp[i] = 1 ~ i - 1까지의 원소들에서, i번째 원소보다 값이 작은것들 중, 가장 큰 dp값 + 1


구현

백준 11053: 가장 긴 증가하는 부분 수열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001], dp[1001], ans, N;
//dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이
int main() {
    ios_base::sync_with_stdio(false);
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        cin >> arr[i];
        int here = 0;
        for(int j = 1; j < i; ++j) {
            if(arr[i] > arr[j])
                here = max(here, dp[j]);
        }
        dp[i] = here + 1;
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}
cs


lower bound

O(N log  N) 알고리즘을 보기전에, lower bound라는 것을 알아야 합니다. 어떠한 정렬된 배열 arr에서 어떠한 값 val의 lower bound란 arr을 정렬된 상태로 유지하면서 val이 삽입될 수 있는 위치들 중 가장 인덱스가 작은 것입니다. 가령 [1, 3, 3, 6, 7] 이라는 배열에서 1의 lower bound는 1이고, 3의 lower bound는 2 이며, 5의 lower bound는 4입니다. (이 글에서 배열의 인덱스는 1부터 시작한다는 것에 유의해주세요). 또한 upper bound라는 개념도 있는데, 이것은 반대로 삽입될 수 있는 위치들 중 가장 인덱스가 큰 것입니다.


lower bound는 이진 탐색을 통해 log N 시간에 구할 수 있으며, C++의 경우 STL에 이미 구현이 되어 있기 때문에 직접 구현할 필요도 없습니다. C++의 lower_bound 함수에 대해서는 아래의 링크를 참고하시기 바랍니다. 


http://ko.cppreference.com/w/cpp/algorithm/lower_bound


O(N log N) 알고리즘

O(N^2) 알고리즘은 i번째 원소 직전에 올 수 있는 원소들중 가장 길게 만들 수 있는 것을 찾을 때, 1 ~ i - 1 까지의 모든 원소를 순회합니다. 따라서 이 과정에 O(N)의 시간이 걸리게 되고, 전체 시간복잡도는 O(N^2)이 됩니다. O(N log N) 알고리즘은 이 과정을 이진 탐색을 통해 O(log N) 시간에 수행하고, 따라서 전체 시간복잡도는 O(N log N)이 됩니다. 


이 알고리즘은 다음과 같은 리스트 L을 업데이트하며 동작합니다. 

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

따라서 L의 크기가 곧 현재까지 만들 수 있는 LIS의 길이이며, 처음에는 빈 리스트로 시작합니다.


수열의 원소들을 앞에서부터 순회하며, 다음과 같은 과정을 통해 L을 업데이트 합니다. (순회하는 과정에서 이번 원소를 here 이라고 하겠습니다.)


1. L이 비어있거나, 현재 L의 마지막 원소보다 here이 더 클 경우

L의 뒤에 here을 추가합니다. 왜냐하면 지금까지 만들 수 있는 가장 긴 증가하는 부분수열의 마지막 원소보다 here이 더 크기 때문에, here을 마지막으로 만들 수 있는 LIS의 길이는 현재 L의 길이 + 1 이기 때문입니다.


2. 그렇지 않을 경우

L배열에서 here의 lower bound를 찾아서, 그 자리를 here로 바꿉니다. 


초기의 빈 리스트 L은 정렬되어 있다고 볼 수 있고, 위의 과정으로만 L을 변형하면 정렬된 상태를 깨지 않습니다. 따라서 2번 과정에서 이진 탐색을 사용할 수 있습니다. 위의 과정을 마치고나서, L의 길이가 이 수열에서 LIS의 길이입니다. 



3

2  

5 

2  

3 

1  

4 
이 수열을 대상으로한 이 알고리즘을 수행했을 때, L의 변화 과정을 살펴보겠습니다.




초기 L은 비어있기 때문에, 3을 추가합니다.

3

현재 L에서 2의 lower_bound는 1이기 때문에, 인덱스 1에 2를 넣습니다.

2


현재 L의 마지막 원소인 2보다 5가 크기 때문에, 뒤에 5를 추가합니다.

2
5

현재 L에서 2의 lower_bound는 1이기 때문에, 인덱스 1에 2를 넣지만, 변화는 없습니다.

2
5 


현재 L에서 3의 lower_bound는 2이기 때문에, 인덱스 2에 3을 넣습니다.

2
3

현재 L에서 1의 lower_bound는 1이기 때문에 인덱스 1에 1을 넣습니다.
1
3

현재 L의 마지막 원소인 3보다 4가 더 크기 때문에, 뒤에 4를 추가합니다.

1
3
4

모든 과정이 끝났습니다. 이 때 L의 크기인 3이 이 수열에서 LIS의 길이가 됩니다. 

구현

백준 11053: 가장 긴 증가하는 부분 수열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
 
int L[1001], len, N;
int main() {
    ios_base::sync_with_stdio(false);
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        int here;
        cin >> here;
        auto pos = lower_bound(L + 1, L + len + 1, here);
        *pos = here;
        if(pos == L + len + 1)
            len++;
    }
    cout << len;
    return 0;
}
cs

그렇다면 왜 하필 lower bound의 값을 업데이트 하는걸까요?

그 이유는 우선 lower bound 왼쪽의 값들은 here보다 작기 때문에, L배열의 정의상 here로 바꿀 수 없습니다.

또한 lower bound의 오른쪽 값들도 역시 바꿀 수 없는데, 이유는 오른쪽의 값들을 마지막으로 하는 LIS는, 그 이전 원소로 here 이상의 값을 가질 수 밖에 없습니다. 따라서 역시 here이 그값을 대체할 수 없습니다.


LIS를 구성하는 원소들까지 구하는 방법


이 알고리즘을 수행했을 때, 마지막에 L에 들어있는 원소들이 LIS의 구성 요소들은 아닙니다. L배열로는 단지 LIS의 길이만 알 수 있습니다.
만약 LIS를 구성하는 원소들이 무엇인지도 알고싶다면, 추가적인 처리가 필요합니다.
또 다른 배열 P를 하나 만들고, P[i] 에 수열의 i번째 원소가 L내에서 위치하는 인덱스를 저장합니다.
위의 예시에서 P배열을 만들면 최종 결과는 다음과 같습니다.

1
1
2
1
2
1
3

P배열에서, 오른쪽에서 가장 처음 3이 나타나는 곳의 인덱스 7
그 다음부터 가장 처음 2가 나타나는 곳의 인덱스 5
그 다음부터 가장 처음 1이 나타나는 곳의 인덱스 4
이렇게 3개가 수열에서 LIS를 구성하는 원소들의 인덱스입니다.  따라서 이 수열의 LIS는 [2, 3, 4]가 됩니다.

구현
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
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001], L[1001], P[1001], len, N;
void backtrace(int idx, int num) {
    if(idx == 0)
        return;
    if(P[idx] == num) {
        backtrace(idx - 1, num - 1);
        cout << arr[idx] << " ";
    }
    else {
        backtrace(idx - 1, num);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        cin >> arr[i];
        auto pos = lower_bound(L + 1, L + len + 1, arr[i]);
        *pos = arr[i];
        P[i] = distance(L, pos);
        if(pos == L + len + 1)
            len++;
    }
    cout << len << "\n";
    backtrace(N, len);
    return 0;
}
cs




저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

강결합 컴포넌트 (Strongly Connected Component)  (9) 2017.02.13
P-NP 문제  (2) 2017.02.13
이분 그래프와 홀수 사이클  (0) 2017.02.12
,

티스토리툴바