LIS(최장 증가 부분열)

길이가 n인 수열 a0, a1, ... , an - 1이 있습니다. 이 수열의 증가 부분열 중 최장의 것의 길이를 구하세요. 단 증가 부분열이란 모든 i < j 에서 ai < aj를 만족하는 부분열을 말합니다.

!제약

1 <= n <= 1000

1 <= ai <= 1000000

 

위의 최장 부분열 을 구하는 문제는 유명한 dp문제중 한개이다.

dp로 문제를 해결하기 위하여 점화식을 정의해 보자.

dp[i] = a[i]를 마지막 원소로 갖는 부분열의 길이의 최댓값

dp[i] = max(dp[i], dp[j] + 1) (0 <= j < n, dp[i] < a[i])

 

위의 식을 코드로 옮기면 아래와 같다.

int dp[n];

int ret = 0;

int main(){

  for(int i = 0; i < n; ++i){

    if(dp[i] == -1)  dp[i] = 1;

    for(int j = 0; j < i; ++j){

      if(dp[j] < a[i])

  dp[i] = max(dp[i], dp[j] + 1);

    }

    ret = max(ret, dp[i]);

  }

  cout << ret << endl;

}

 

위와 같은 점화식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 n = 1000인 지금과 같은 경우에는 제한 시간안에 문제를 해결할 수 있지만 예를들어 n = 1000000일 경우에는 제한시간내에 문제를 해결할 수 가 없다. 그러므로 우리는 새로운 점화식이 필요한데 위의 점화식에서 사용한 값들의 역할을 바꿔서 생각해보자. 위의 점화식에서는 이러했다.

dp[i] = 마지막 원소가 a[i]인 부분수열의 최대 길이.

dp의 인덱스와 dp의 값의 위치를 바꾸면 아래와 같은 점화식이 세워진다.

dp[i] = 길이가 i + 1인 부분수열 중에서 가장 작은 마지막 원소

위와 같은 점화식을 통해서 문제를 풀기위해 값이 어떤식으로 변화 되어 질 것인지 생각해보자.

dp[i] = min(dp[i], a[j]) (i = 0 || dp[i - 1] < dp[i])

1. dp테이블을 최초에 INF(큰값)으로 초기화 한다,

2. dp테이블에서 이미 구해진 값중에 a[j]보다 큰 값이 있다면 해당 dp값을 a[j]로 초기화 한다. (여기서 dp테이블에 대한 순회는 멈추면 되는것이 뒤쪽에 이미 구해진 dp값은 바뀌는 것이 불가능 하다. 왜냐하면 앞쪽 값이 이미 현재 a[j]보다 작기때문에 앞쪽값이 바뀌는 현재 상황에서 뒤쪽값을 바꾸면 길이가 x인ㅣlis의 마지막값 과 x + 1인 lis의 마지막 값 ... 이미구해진 모든 dp의 값이 a[j]가된다. 그리고 아직 구해지지 않은 값은 바뀔 수가 없는 것은 (3.)을보면 이해할 수 있다.)

3. 이미 구해진 값중에서 a[j]보다 큰값이 없다는 것은 이미 구해진 lis의 길이의 마지막 원소는 전부 a[j]보다 크다 그러므로 지금까지 구해진 길이의 lis보다 1더 긴 lis의 마지막 원소는 a[j]가된다.

 

위의 로직의 코드는 아래와 같다.

 

int dp[MAX_N];

 

int main() {

  fill(dp, dp + n, INF);

  for(int i = 0; i < n; ++i)

    *lower_bound(dp, dp + n, a[i]) = a[i];

  cout << lower_bound(dp, dp + n, INF) - dp << endl;

}