LIS 알고리즘 (2)

가장 긴 증가하는 부분 수열 (LIS) - 2

• LIS 배열 구하기
• 백준 2568 전깃줄 - 2
• 백준 2550 전구

• LIS 알고리즘 (1)
  https://velog.io/@sunjoo9912/LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1

LIS 배열 구하기

• 기존의 이분 탐색을 이용한 LIS 알고리즘을 수행한다
  -> 수행하면서 A[i]가 vt벡터의 몇 번째 인덱스에 들어가는지
  -> record 벡터에 저장
• record 배열의 제일 뒤부터 탐색하여
  -> record[i]에 저장된 인덱스가 순차적인 내림차순이 된다면
  -> ret 벡터에 push_back(A[i]) 연산을 한다.
• 최종적으로 ret 벡터를 역순으로 바꾸면 LIS 배열이 구해진다

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	int A[1001] = { 0 };

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];
	
	vector <int> vt;
	vector <int> record;
	vector <int> ret;


	// record 벡터에 A[i]가 vt벡터에 저장되는 위치 저장 
	int idx = 0;
	vt.push_back(A[0]);
	record.push_back(0);

	for (int i = 1; i < n; i++) {
		if (vt.back() < A[i]) {
			vt.push_back(A[i]);
			record.push_back(++idx);
		}
		else {
			auto it = lower_bound(vt.begin(), vt.end(), A[i]);
			*it = A[i];
			record.push_back(it-vt.begin());
		}
	}

	// lis 추적
	int flag = idx;
	for (int i = n-1 ; i >= 0; i--) {
		if (record[i] == flag) {
			ret.push_back(A[i]);
			flag--;
		}
		if (flag == -1)
			break;
	}
	reverse(ret.begin(), ret.end());

	for (auto it = ret.begin(); it != ret.end(); it++)
		cout << *it << " ";
	cout << "\n";

	return 0;
}

• 예. A : 4 2 6 7 9 1 3 10
  vt : 4
  record : 0
  vt : 2
  record : 0
  vt : 2 6
  record : 0 1
  vt : 2 6 7
  record : 0 1 2
  vt : 2 6 7 9
  record : 0 1 2 3
  vt : 1 6 7 9
  record : 0 1 2 3 0
  vt : 1 3 7 9
  record : 0 1 2 3 0 1
  vt : 1 3 7 9 10
  record : 0 1 2 3 0 1 4
  ret : 10 9 7 6 2
  ret : 2 6 7 9 10 (LIS 배열)

➖

백준 2568 전깃줄 - 2

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2568-%EC%A0%84%EA%B9%83%EC%A4%84-2

백준 2550 전구

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2550-%EC%A0%84%EA%B5%AC

📌참고 자료

• upper_bound, lower_bound 의 인덱스
  https://www.crocus.co.kr/913

  이터레이터를 반환받지 않고 인덱스를 반환 받기 위해서는
  lower_bound( ~ ) - vector.begin()
  upper_bound( ~ ) - vector.begin()

• 벡터 역순 저장
  https://starrykss.tistory.com/597

• LIS 추적
  https://yhwan.tistory.com/21