코딩테스트에서 자주 쓰는 C++ STL 라이브러리, 자료구조, 알고리즘 정리(4) - 최장증가부분수열, LIS(Longest Increasing Subsequence)

최장증가부분수열 Longest Increasing Subsequence

문제 예시)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

• 관련 문제

  • 백준 11055번 가장 큰 증가 부분 수열

  • 백준 1965번 상자 넣기

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

LIS를 해결하는 방법은 두가지가 있다. N의 크기, 문제의 조건에 따라 아래 두 방법중 적절한 것을 사용하면 된다.

• 방법 1 : 이중 for-loop

  • 시간복잡도 : O(n^2)

  • dp 배열은 i 번째 원소가 가질 수 있는 최대증가수열의 길이를 뜻한다.

  • 수열 A = {10, 20, 10, 30, 20, 50} 인 경우 dp[4]는 3이다. {10, 20, 10, 30, 20 ...}

  • n이 10,000을 넘어가면 시간초과가 발생할 수 있다.

  int arr[MAX]; // 인덱스마다 각 입력값
  int dp[MAX]; // 인덱스마다 각 증가 수열의 길이
  int max = 0;
  dp[0] = 1;
  for(int i=1;i<N;i++) {
   dp[i] = 1;
   // i 를 기준으로 인덱스 0 에서부터 i-1까지 체크한다 
   // 길이를 기준
    for(int j=0;j<i;j++) {
        if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
            // 증가 수열
            dp[i] = dp[j] + 1;
        }
    }
    if (max < dp[i]) {
        max = dp[i];
    }
  }

• 방법 2 : 이분 탐색

  • 시간복잡도 : O(nlogn)

  • 배열 마지막 요소보다 새로 들어오는 수가 크다면, 배열에 넣는다.

  • 그렇지 않다면, 그 수가 들어갈 자리에 들어가 있는 값을 교체한다(lower_bound 로 들어갈 자리를 찾음)

    lower_bound : 주어진 값보다 작지 않은(같거나 큰) 첫번째 원소의 iterator를 반환

  • dp 벡터의 사이즈가 LIS가 된다

  • 단점 : 정답밖에 모른다. 경로를 역추적 할 수 없다.

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
using namespace std;
// LIS로 풀자
int n;
int answer;
vector<int>v;
vector<int>lis; // 인덱스마다 각 증가 수열의 길이

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp; cin >> tmp;
        v.push_back(tmp);
    }
    lis.push_back(v[0]);
    for (int i = 1; i < n; i++) {                
        if (lis.back() < v[i]) { // lis의 맨 뒤의 원소보다 큰 값이 들어오면 삽입
            lis.push_back(v[i]);
        }
        else { // lis의 맨 뒤 원소보다 작은 값이면, 그 원소가 들어갈 위치에 삽입
            int idx = lower_bound(lis.begin(), lis.end(), v[i]) - lis.begin();
            lis[idx] = v[i];
        }

    }
    answer = lis.size();
    cout << answer;
    return 0;
}