[백준/12015/C++] 가장 긴 증가하는 부분 수열 2

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

---

문제 )

---

입출력 )

---

예제 입력 )

---

풀이 )

이분탐색 O(n log n)

입력받은 수열을 보면 

10  20  10  30  20  50

증가하는 수열이므로 말 그대로 차례대로 증가하는 수의 갯수를 의미한다.

이렇게 총 길이가 4가 나온다.

이 문제의 시간은 1초로 이분탐색의 시간복잡도는 O(log n)으로 이분탐색을 이용하여 풀면 시간초과가 뜨지 않는다.

(나는 STL에 Lower_Bound & Upper_bound를 사용할 것이다.)

 

알고리즘 로직 )

수열을 차례로 입력받을 때 앞의 수와 비교하여

크다면? 벡터에 Push하고 Num++ 해준다.

작다면? lower_bound를 찾고 그 자리에 입력받은 수를 넣어준다.

=> 삽입되는 수보다 크거나 같은 첫번째 원소의 위치를 반환

 

---

코드 )

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

vector<int> v;
int n, num;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

	v.push_back(-1);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		if (input > v.back())
		{
			v.push_back(input);
			num++;
		}
		else
		{
			vector<int>::iterator low = lower_bound(v.begin(), v.end(), input);
			*low = input;
		}
	}
	cout << num;
}

 

---

코드 설명

---

lower_bound와 upper_bound는 이진탐색트리를 기반으로 되어있다.

(이진탐색은 기본적으로 정렬이 되어있어야한다.)

#include<algorithm> 헤더를 추가해주어야 사용할 수 있다.

 

1. 수열 값을 하나씩 입력받는다.

2-1. 입력받은 값이 벡터의 끝보다 큰 경우

=> 벡터에 삽입 + num++

if (input > v.back()) {
	v.push_back(input);
	num++;
}

 

2-2. 입력받은 값이 벡터의 끝보다 크지 않은 경우

=> lower_bound로 입력받은 값보다 큰 곳이 배열 몇번째에 있는지 알아보기

else {
	vector<int>::iterator low = lower_bound(v.begin(), v.end(), input);
	*low = input;
}

---