가장 긴 증가하는 부분 수열5

가장 긴 증가하는 부분 수열 이 문제를 한 번 보고오도록 하자.

이 문제같은 경우 최대범위가 작기때문에 이중반복문으로 O(N^2)으로 최대의 길이를 구했다.

하지만 부분 수열5같은 경우 백만이기 때문에

1000000 * 1000000 이면 너무 크기때문에 nlogn으로 구해주어야한다.

lower_bound의 원리를 정확히 알아야 했고,
이를 통해 trace를 구하는 문제이다.

또한 stack에 넣을 때도 len - 1과 같을 때만 넣는 것을 확인을 해주어야한다.

후기

1시간 반정도 했는데 못 품.

"trace"개념이랑 가장 긴 부분 수열 조차 생각이 안났다.

struct Info
{
	ll length;
	ll prevVal;
	ll curIdx;
};

Info dp[MAX];

이런식으로 구현을 할려고 했는데 이전에 배웠던 것도 까먹고 생각도 안났다. (훑는 식의 복습이라도 해야하는 듯하다)

lower_bound

#include <bits/stdc++.h>
using namespace std;

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 주소값 출력
int main()
{
	auto lowerPos = lower_bound(arr, arr + 10, 5);
	cout << lowerPos << endl;
	return 0;
}
// 출력 결과는 iterator 주소값이 반환된다.


// index 출력
{
	auto lowerPos = lower_bound(arr, arr + 10, 5);
	cout << lowerPos - arr << endl;
	return 0;
    // 5라는 값이 있는 인덱스를 출력한다.
}

// 이렇게 해도 인덱스를 출력한다.
{
	auto lowerPos = lower_bound(arr, arr + 10, 5) - arr;
	cout << lowerPos << endl;
}

lower bound 값이 없을경우 가장 근접한 값의 인덱스를 반환한다

lower_bound는 이분탐색으로 값을 O(n Log n)으로 탐색해주는 함수이다.

값이 없는 경우 가장 가까운 위치에 있는 iterator를 반환해준다.

cpp

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000004
#define endl "\n"

int n, lis[MAX], len, num;
pair<int, int> ans[MAX];
stack<int> stk;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> num;
		// 주소값 가르킨다. 
		auto lowerPos = lower_bound(lis, lis + len, num);
		
		// index가 pos에 할당된다. 
		int pos = (int)(lower_bound(lis, lis + len, num) - lis);
		
		// num을 찾았는데 값이 없을 경우 (*iterator는 0을 반환한다) 
		if (*lowerPos == 0) ++len;
		
		*lowerPos = num;
		
		// 이부분이 trace에 해당? 하는 부분. 
		ans[i].first = pos;
		ans[i].second = num;
	}
	
	cout << len << endl;
	
	for (int i = n - 1; i >= 0; --i)
	{
		if (ans[i].first == len - 1) 
		{
			stk.push(ans[i].second);
			--len;
		}
	}
	
	while (stk.size())
	{
		cout << stk.top() << " ";
		stk.pop();
	}
	
	return 0;
}