반도체 설계 (백준 - 2352번)

 

동적계획법(Dynamic Programming)을 사용하여 가장 긴 최장증가수열(LIS)을 구하는 문제이다.

 

동적계획법 : https://lipcoder.tistory.com/49

동적계획법(Dynamic Programming)

최장증가수열 : https://lipcoder.tistory.com/50

최장증가수열 - LIS(Longest Increasing Subsequence)

 

하지만 시간제한이 존재하기 때문에 시간복잡도가 O(n^2)이 나오는 알고리즘을 쓰면 시간 초과가 나온다. 그래서 각 원소마다 그 원소의 이전 값들을 쭉 훑어보며 LIS를 찾는 알고리즘은 쓸 수 없다. 

 

해결법은 이전 값들을 찾을때 이진탐색을 사용하여 O(nlogn)의 시간복잡도를 가지도록 구현하는 것이다. 

 

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int input = 0;
	cin >> input;

	// 이전 값들을 저장할 벡터
	vector<int> vt;
	vt.push_back(0);
    
	int* list = new int[input + 1];
	list[0] = 0;
	for (int i = 1; i <= input; ++i)
	{
		cin >> list[i];
	}

	int max = 0;
	for (int i = 1; i <= input; ++i)
	{
		int length = 0;
		// 만약 원소가 이전 값들보다 큰 경우
		if (vt.back() < list[i])
		{
			// LIS를 구하고 원소를 벡터에 추가한다.
			length = (vt.size() - 1) + 1;
			vt.push_back(list[i]);
		}
		//  원소가 크기상 벡터 사이에 들어가는 경우
		else
		{
			// 이진 탐색을 이용하여 원소에 알맞은 위치를 찾는다.
			auto iter = lower_bound(vt.begin(), vt.end(), list[i]);
			// 위치 정보를 활용하여 LIS를 구한다.
			int dist = distance(vt.begin(), iter);
			length = (dist - 1) + 1;
			// 그 위치에 원소를 현재 원소값으로 덮어쓴다.
			vt[dist] = list[i];
		}
		if (max < length)
			max = length;
	}

	cout << max << endl;
	delete[] list;
}