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

(문제링크)


가장 긴 증가하는 부분수열은 LIS(Longest Increasing Subsequence)라고 불리는 유명한 문제이다.


이 문제는 다음과 같은 방법으로 접근했다.

  • 먼저 브루트포스가 가능한지 생각해 보았다. 수열의 최대 크기는 10001000이고, 이 수열이 오름차순일때 중복 없이 만들수 있는 모든 부분 집합은 아무것도 없는것을 제외한 2n12^{n}-1개 이다.(수열이 포함되었거나 포함되지 않았거나기 때문에 예측하기 간단하다) 그래서 브루트포스만으로는 불가능하다.
  • 이때 부분수열 중 대부분은 서로 중복되는 부분이 있고, 중복되는 LIS의 길이는 항상 같은 값이 나오기 때문에 이것을 캐싱한다면 연산의 수는 엄청나게 줄어들게 된다. 이때 한 시점마다 그 시점의 LIS 외에 다른 부분 수열은 절대 답의 후보가 될 수 없다.(설명하기 어려우니 일단 재끼자)

최종 코드

for(int i = 1; i <= n; i++){
  d[i] = 1;
  for(int j = 1; j < i; j++){
    if(a[j] < a[i] && d[i] < d[j] + 1) d[i] = d[j] + 1;
  }
}

가장 긴 감소하는 부분 수열

LIS로 풀고 뒤집어도 된다.

for(int i = 1; i <= n; i++){
  d[i]=1;
  for(int j = 1; j < i; j++){
    if(a[i] < a[j] && d[i] < d[j] + 1){
      d[i] = d[j] + 1;
    }
  }
}