[BOJ] 11053: 가장 긴 증가하는 부분 수열

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

BOJ - 가장 긴 증가하는 부분 수열

문제 유형: 다이나믹 프로그래밍, LIS(가장 긴 증가하는 부분 수열), 이진 탐색

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

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

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

LIS(Longest Increasing Subsequence)의 전형적인 문제이다.

1. dp를 이용한 방법 - O(n^2)

n길이의 배열 dp와 arr이 있다고 해보자. arr은 원본 수열이고, dp[i]는 arr[i]를 마지막으로 하는 가장 큰 값이다.

배열을 순차적으로 순회하면서, 자신 이전의 인덱스들의 값들 중에서 자신보다 작으면서 dp값이 가장 큰 값을 가져와서 가장 긴 값을 만든다.

dp배열에서 가장 큰 값을 찾아서 반환하면 된다.

 

 

2. 이진탐색을 이용한 방법 - O(nlogn)

lis배열은 현재까지 발견된 가장 긴 증가하는 부분수열이다.

arr을 순차적으로 순회하면서, 각 arr[i]를 lis에 넣으려고 시도한다.

 

만약 arr[i]가 현재 lis에 있는 요소들보다 크다면, 맨 뒤에 붙인다.

아니라면, arr[i]를 lower_bound로 이용해서 위치를 찾아 삽입한다.

주의할 점은, 이 lis배열은 실제 LIS가 아니다. 로직을 자세히 살펴보면, 순서가 뒤섞여있음을 알 수 있다.

 

 

코드

C++

dp를 이용한 풀이

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<int> dp(n);
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  dp[0] = 1;
  for (int i = 1; i < n; ++i) {
    int maxLen = 0;
    for (int j = 0; j < i; ++j) {
      if (arr[i] > arr[j]) {
        maxLen = max(maxLen, dp[j]);
      }
    }
    dp[i] = maxLen + 1;
  }

  cout << *max_element(dp.begin(), dp.end()) << "\n";

  return 0;
}

 

이진탐색을 이용한 풀이

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  vector<int> lis;

  for (int i = 0; i < n; ++i) {
    auto it = lower_bound(lis.begin(), lis.end(), arr[i]);

    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
  }
  cout << lis.size() << "\n";

  return 0;
}