최장 증가 부분 수열 찾기 | 역추적 (Longest Increasing Subsequence Tracking)

2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence)

지난 포스팅에서 LIS로 찾은 결과는 부분 수열의 최장 길이에 대한 정보만을 가지고 있을 뿐, 그 자체가 부분 수열이 될 수 없다는 점을 강조했다. 

입력 배열

LIS 역추적을 위해 pair 자료형 배열을 만들고 다음과 같이 정의하였다. 

pair<int,int> LIS[MAX_SIZE] // first = 값, second = 인덱스

그리고 매번 arr배열을 탐색하면서 2가지 규칙으로 i번째 인덱스 앞에 올 인덱스 j (j<i)값을 의미하는 pre[i]를 채워 나갈것이다. pre 배열은 -1로 초기화 한다. (pre[i] 가 -1 이라는 것은 i번째 인덱스는 부분 수열 중 맨앞 원소)

lastidx는 LIS 배열의 마지막 값보다 큰 인덱스로 전체 동작에 대한 부분 수열 결과의 실제 마지막 값에 대한 인덱스를 의미한다. 또한, _size는 LIS의 길이 변수로 정의하면 (arr 배열 탐색 전 arr[0]의 값을 LIS 배열에 넣으므로 초기값은 1)

1. LIS[_size-1].first 값 (LIS의 마지막 원소)보다 arr[i] 값이 큰 경우 

i가 1인 경우 arr[i] = 20, LIS[_size-1].first = 10 이므로 첫번째 규칙을 따름 (_size = 1)

		if (arr[i] > LIS[_size-1].first) {
			lastidx = i;
			pre[i] = LIS[_size - 1].second;
			LIS[_size++] = { arr[i],i };
			continue;
		}

2. LIS[_size-1].first 값이 arr[i] 보다 크거나 같은 경우

LIS 배열에서 arr[i] 보다 크거나 같은 제일 작은 원소 LIS[idx].first를 찾아서 LIS[idx-1].second를 pre[i]로 저장한다.

i 가 2인 경우 arr[i] = 15, LIS[_size-1].first = 20이므로 두번째 규칙을 따름 (_size = 2)

		int s = 0, e = _size - 1;
		int mid;
		int idx;
		while (s <= e) {
			mid = (s + e) / 2;
			if (LIS[mid].first >= arr[i]) {
				e = mid - 1;
				idx = mid;
			}
			else {
				s = mid + 1;
			}
		}
		if (!idx) {
			pre[i] = -1;
		}
		else {
			pre[i] = LIS[idx - 1].second;
		}
		LIS[idx] = { arr[i],i };

 

마지막으로 lastidx 부터 인덱스가 -1이 될 때까지 (처음 원소) 스택에 집어 넣고 거꾸로 출력하면 가장 긴 증가하는 부분 수열을 얻을 수 있다.

>> 백준 문제

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <string>
#include <algorithm>
#define MAX_SIZE (1000001)
using namespace std;
typedef long long ll;
int n;
stack<int> s;
int arr[MAX_SIZE], pre[MAX_SIZE];
pair<int, int> LIS[MAX_SIZE];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	memset(pre, -1, sizeof(pre));
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	LIS[0] = { arr[0],0 };
	int _size = 1;
	int lastidx = 0;
	for (int i = 1; i < n; i++) {
		if (arr[i] > LIS[_size-1].first) {
			lastidx = i;
			pre[i] = LIS[_size - 1].second; // i번째 인덱스의 이전 값은 LIS 마지막 배열의 인덱스이다.
			LIS[_size++] = { arr[i],i };
			continue;
		}
		int s = 0, e = _size - 1;
		int mid;
		int idx;
		while (s <= e) {
			mid = (s + e) / 2;
			if (LIS[mid].first >= arr[i]) {
				e = mid - 1;
				idx = mid;
			}
			else {
				s = mid + 1;
			}
		}
		if (!idx) {
			pre[i] = -1;
		}
		else {
			pre[i] = LIS[idx - 1].second;
		}
		LIS[idx] = { arr[i],i };
	}
	for (int i = lastidx; i != -1; i = pre[i]) {
		s.push(arr[i]);
	}
	cout << _size<<"\n";
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}
}