LIS(Longest Increasing Subsequence - 최장 증가 수열) 알고리즘 (2)

LIS(Longest Increasing Subsequence - 최장 증가 수열) (2)

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

---

!본 글에서는 최장 증가 수열의 길이만 구한다. 수열에 포함된 수는 다양한 방법을 통해 얻을 수 있다!

 

가장 긴 증가하는 부분수열(이하 LIS)의 길이를 찾기위한 기본적인 알고리즘 설명은 여기(링크) 있다.

이전글에서 LIS의 길이를 구하기 위해 O(N^2)만큼의 시간이 소요된다고 했었다.

본 글에서는 이를 O(N*logN)으로 줄이는 알고리즘에 대해서 설명한다.

 

이 글을 이해하기 위해선 반드시 여기(링크)의 설명을 정확히 이해해야 한다! 

 

1. LIS의 길이를 O(N^2)으로 구하는 방법 : 여기(링크)

2. LIS의 길이와 수열을 O(N^2)으로 구하는 방법 : 여기(링크)

3. LIS의 길이와 수열을 O(N*logN)으로 구하는 방법 : 여기(링크)

 

설명

---

이 알고리즘을 구현하기 위해선 <algorithm>헤더파일에 있는 lower_bound와 upper_bound에 대한 이해가 필요하다. 구글링해서 알아오자.

 

이 알고리즘의 기본 구성은 이전글에서 설명했던 방법과 유사하다.

이전글에서는 num[]을 순환하며(O(N)) 최적의 index(num[index]가 자신보다 작고, dp값은 가장 큰)를 찾기위해 O(N)만큼의 시간이 걸려 총 O(N^2)의 시간이 걸렸는데, 배열을 순회하는 O(N)은 어떤 방법을 써도 줄일 수 없기 때문에 최적의 위치를 찾을 때의 시간을 O(logN)으로 줄이는 것을 중점적으로 생각한다.

 

먼저 알고리즘의 과정에 대해 안 후, 과정에 대한 설명은 나중에 한다.

기본적으로 배열이 하나 더 필요하다. 이 배열은 LIS의 길이를 알기 위한 배열이다.

입력 배열 num[]과 추가로 선언한 vector L이 있다고 가정하자. 과정은 다음과 같다.

 

0. num배열을 순환한다. (현재 인덱스 = i)

A. L이 비어있다면 num[i]를 push한다.

B-1) L의 마지막 값보다 num[i]가 크면 push한다.

B-2) 아니라면 L의 lower_bound(L.begin(), L.end(), num[i])의 값을 num[i]로 바꿔준다.

 

예시를 보며 따라가보자. {9, 8, 8, 9, 11, 10, 14}라는 배열이 있다고 가정한다.

 

i=1) 처음에는 L이 비어있으므로 9를 push한다. (조건 A)

num	9	8	8	9	11	10	14
vector L	9

i=2) L에서의 8의 lower_bound를 8로 바꿔준다. (조건 B-2)

num	9	8	8	9	11	10	14
vector L	8

i=3) L에서의 8의 lower_bound를 8로 바꿔준다. (조건 B-2)

num	9	8	8	9	11	10	14
vector L	8

i=4) L의 마지막 값보다 9가 크므로 9를 push한다. (조건 B-1)

num	9	8	8	9	11	10	14
vector L	8	9

i=5) L의 마지막 값보다 11이 크므로 11을 push한다. (조건 B-1)

num	9	8	8	9	11	10	14
vector L	8	9	11

i=6) L에서의 10의 lower_bound를 10으로 바꿔준다. (조건 B-2)

num	9	8	8	9	11	10	14
vector L	8	9	10

i=7) L의 마지막 값보다 14가 크므로 14를 push한다. (조건 B-1)

num	9	8	8	9	11	10	14
vector L	8	9	10	14

 

이로써 모든 단계가 끝났다. 이때 L의 크기가 LIS의 길이가 된다. lower_bound 연산은 O(logN)이므로 배열을 도는시간 O(N)과 곱해져 총 시간복잡도는 O(N*logN)이다.

 

이제 이 과정에 대해 이해해보자.

기존 LIS에서 배열을 돌며 최적의 위치를 찾는다는 것은 자신보다 작으면서 DP의 값은 가장 큰 index를 찾는 것이었다. (이유는 알고있어야 한다) L의 역할이 바로 이것이다. 예를 들어 i=6일때의 과정을 다시 살펴보자.

i=5일때 L은 {8, 9, 11}이었다.

이말은 9까지 포함했을때 LIS의 길이는 2이고 11까지 포함했을 때 LIS의 길이가 3이라는 뜻이다.

i=6일때 10이 추가되면 10보다 작은 9를 포함했을 때 LIS의 길이가 2이기 때문에 +1을 한 3이 되기 위해 11을 가능한 더 작은 숫자인 10으로 바꾸는 것이다.

그런데 만약바꾸지 않는다면 어떻게 될까?

 

i=5일때 L={8, 9, 11} 상태에서 10이 들어왔을 때 바꾸지 않는다고 가정해보자.

i=6일때 L={8, 9, 11} 이 유지될것이다. 이때 10.5라는 숫자가 들어온다면 어떻게 될까?

i=7일때 L={8, 9, 11} 이 되어 현재까지 LIS의 길이는 3이 되지만 실제로는 {8, 9, 10, 10.5}가 되어 4가된다.

 

이해가 되는가? 잘 되지 않는다면 다시 정독하자.

 

또 주의해야 할 점이있다.

vector L은 LIS의 길이만을 나타내기 위한 배열이지, 절대 LIS의 요소를 포함하는 배열이 아니다.

 

예를 들어 {9,10,8}라는 배열이 있다고 가정해보자.

위에서 언급한 과정을 거치면 L={8, 10}이 되는데 이는 실제 LIS 배열인 {9, 10}과는 다르다.

이 점 주의하자!

 

구현

---

int *num = new int[N];
int a;
vector <int> L;
for(int i=0;i<N;i++){
    cin>>a;
    num[i]=a;
    if(L.size()==0) L.push_back(num[i]);
    else{
        if(L[L.size()-1]<num[i]) L.push_back(num[i]);
        else{
            *(lower_bound(L.begin(),L.end(),num[i]))=num[i];
        }
    }
}

최종적으로 L의 크기가 LIS의 길이이다! 

 

이 코드를 그대로 가져다 쓰면 백준 12015번 (가장 긴 증가하는 부분수열2)를 풀 수 있다. 무려 골드 2티어이다!