알고리즘 :: 백준 :: DP :: 14003 :: LIS

LIS(최장 증가 부분수열) 문제

<문제링크>: https://www.acmicpc.net/problem/14003

• LIS 문제는 정말 유명하며 동시에 많은 변조 문제들이 있다.
• LIS 문제의 핵심에 대해 파악해보도록 하자.

문제를 풀기 전

• 모든 요소를 비교해보는 bruteforce 방식으로는 제한시간내에 절대 풀 수 없습니다. 따라서 DP 또는 greedy 방식으로 생각해봅니다.
• i번째 요소가 LIS에 들어갈 경우 몇 번째 인덱스에 들어가게 되는지 기록하는 전략이라면 O(n)~O(nlogn)정도로 제한시간내에 풀 수 있을 것 같습니다. 따라서 이 문제는 DP로 접근하도록 합니다.

문제 풀이법

1. DP를 위한 메모용 벡터 vector<int> memo를 생성합니다.

2. 사용자로부터 입력받는 수열 vec과 memo는 모두 1번 인덱스부터 사용합시다.

3. vec에 다음과 같은 입력이 들어왔다고 가정합니다.

4. vec	1	2	3	4	5	6
   -	4	9	11	5	7	8
   -	0	0	0	0	0	0

   눈으로 보고 알 수 있는 LIS는 LIS: 4, 5, 7, 8입니다.

5. memo	1	2	3	4	5	6
   -	4	9	11

   우선 4가 삽입됩니다. 4보다 9가 크므로 의심없이 삽입합니다.
   9보다 11이 더 크므로 마찬가지로 의심없이 삽입합니다. 이때 vec의 각 요소의 second에는 memo에서의 인덱스가 저장되도록 합니다.

6. memo	1	2	3	4	5	6
   -	4	5	11

   5는 11보다 작은 수입니다. 따라서 그냥 삽입해서는 안됩니다. algorithm헤더파일에 있는 lower_bound함수를 이용해서 5가 들어갈 적절한 인덱스를 찾고 값을 갱신합니다. 따라서 9가 5로 갱신됩니다.

7. memo	1	2	3	4	5	6
   -	4	5	7	8

   vec의 마지막 인덱스까지 순회가 종료되면 memo는 위 표와 같습니다.

8. vec	1	2	3	4	5	6
   -	4	9	11	5	7	8
   -	1	2	3	2	3	4

   vec의 마지막 인덱스까지 순회가 종료되면vec은 위 표와 같습니다.

9. 이제 vec의 마지막 인덱스부터 거꾸로 1번 인덱스까지 순회하면서 LIS를 만들어갑니다. 이때 우리는 stack<int>를 사용해서 역순 출력할 것입니다.

10. stack	0	1	2	3(=top)
    -	8	7	5	4

    순회가 종료되면 스택은 위와 같은 구조를 보입니다. 이제 std::cout << stack.top() << " "과 stack.pop()을 반복하며 역순 출력합니다.

결과화면

설령 본인 코드가 AC를 받았더라도 반드시 위 반례를 돌려봅시다.

• 반례 출처: https://www.crocus.co.kr/681

코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

static int N;
static vector<pair<int, int>> vec;   // 사용자 입력 수열
static stack<int> stk;            // 출력하기 위한 스택
static vector<int> memo;         // DP용 메모 배열

void memoization() {
   for (int i = 1; i <= N; ++i) {
      if (memo.back() < vec[i].first) {   // [분기 1]-LIS 후보 요소 발견
         memo.push_back(vec[i].first);   // Memo 벡터에 삽입   
         vec[i].second = memo.size();   // vec 벡터 second에 Memo 상의 인덱스값 명시
      } else {                     // [분기 2]-Memo 벡터 갱신 요소 발견
         auto itr = lower_bound(begin(memo), end(memo), vec[i].first);
         *itr = vec[i].first;               // Memo 벡터의 해당 요소를 작은 값으로 갱신
         vec[i].second = itr - begin(memo) + 1;   // vec 벡터 second에 Memo 상의 인덱스값 명시
      }
   }
}
void printLIS() {
   int memoIdx = memo.size();
   for (int i = N; i > 0; --i) {
      if (vec[i].second == memoIdx) {
         stk.push(vec[i].first);
         memoIdx--;
      }
   }
   cout << stk.size() << '\n';
   while (!stk.empty()) {
      cout << stk.top() << " ";
      stk.pop();
   } cout << '\n';
}
int main() {
   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
   
   cin >> N;
   vec.resize(N + 1);
   for (int i = 1; i <= N; ++i) { cin >> vec[i].first; vec[i].second = i; }

   memo.push_back(vec[1].first);      // 초기값
   memoization();
   printLIS();
}

배운점

• memo를 사용해서 개수까지는 잘 출력할 수 있었지만, LIS 수열을 만드는 과정을 자꾸 실수해서 오답이 발생했다.
• stack같은 기본 자료구조를 잘 활용할 수 있어야겠다.
• lower_bound같은 STL function을 최대한 활용해보자.