LIS

LIS(Longest Increasing Subsequence)

백준.2568.전깃줄 - 2

최장 증가 수열

보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이 된다.

O(N^2)

index를 순차적으로 증가시켜가며, 이전에 방문했던 0 ~ (index-1)까지의 값을 다시 순회하며 계산했던 값을 이용해 현재 index의 값을 갱신한다.

int lis(vector<int> array) {
  int size = array.size();
  // initialize
  vector<int> dp(size, 1);

  for (int target = 0; target < size; target++) {
    for (int before = 0; before < target; before++) {
      if (array[before] < array[target]) {
        dp[target] = max(dp[target], dp[before] + 1);
      }
    }
  }

  return dp.back();
}

O(N * log_2(N))

시간 복잡도 : O(N * log_2(N))

• N : O(N)으로 배열을 탐색함
• log_2(N) : lower_bound로 최적의 자리를 찾음

배열을 순회하면서 벡터의 맨 뒤 원소와 현재 보고있는 수열의 원소를 비교한다.

수열의 원소가 더 클 시 벡터에 push_back해준 뒤 LIS의 크기(답)을 1증가 시킨다. 수열의 원소가 벡터의 맨 뒤 원소보다 작을 경우 lower_bound를 이용하여 최적의 자리를 찾은 뒤 그 자리의 값을 해당 수열의 원소로 교체한다.

LIS 배열을 구하기 위해선 각 index별로 어떤 값이 있는지 같이 저장해야한다.

int lisLength(vector<int>& nums) {
  int size = nums.size();
  vector<int> lis;

  for (int i = 0; i < size; i++) {
    int target = lower_bound(lis.begin(), lis.end(), nums[i]) - lis.begin();

    if (target == lis.size()) {
      lis.push_back(nums[i]);
    } else {
      lis[target] = nums[i];
    }
  }

  // lis 배열에 LIS를 만들기 위해 임시로 사용된 숫자들이 들어있음
  return lis.size();
}

Longest Non-decreasing Subsequence

LIS 알고리즘에서 lower_bound를 이용해 이전에 나온 값중에서 현재값 이상인 부분을 교채한다.

이를 upper_bound를 이용할 경우 이전에 나온 값중 현재값을 초과하는 부분을 교채하며, 이 과정에서 중복해서 원소가 들어갈 수 있다.

int longestNonDecreasingSubsequence(vector<int> &nums){
  int size = nums.size();
  vector<int> lis;

  for (int i = 0; i < size; i++) {
    int target = upper_bound(lis.begin(), lis.end(), nums[i]) - lis.begin();

    if (target == lis.size()) {
      lis.push_back(nums[i]);
    } else {
      lis[target] = nums[i];
    }
  }

  // lis 배열에 LIS를 구성하는 원소가 들어있음
  return lis.size();
}

LIS를 구성하는 원소 구하기

struct LIS {
  int index, from;
};

vector<int> longestIncreasingSubsequence(int N, vector<int> array) {
  vector<LIS> lis;
  int lis_cache[MAX] = {
      0,
  };
  int index = 0;

  lis_cache[index] = array[0];
  lis.push_back({0, array[0]});
  for (int i = 1; i < N; i++) {
    if (lis_cache[index] < array[i]) {
      index++;
      lis_cache[index] = array[i];
      lis.push_back({index, array[i]});
    } else {
      int new_index = lower_bound(lis_cache, lis_cache + index, array[i]) - lis_cache;

      lis_cache[new_index] = array[i];
      lis.push_back({new_index, array[i]});
    }
  }

  // index + 1은 LIS 배열의 크기를 의미한다.
  // 역순으로 LIS 배열을 구한다. (index를 이용해 역순으로 구함)
  stack<int> s;
  for (int i = N - 1; i >= 0; i--) {
    if (lis[i].index == index) {
      s.push(lis[i].from);
      index--;
    }
  }

  // stack에 역순으로 저장되어있으므로 뒤집어 LIS 배열을 구함
  vector<int> ret;
  while (!s.empty()) {
    ret.push_back(s.top());
    s.pop();
  }

  return ret;
}