[백준] 12015. 가장 긴 증가하는 부분 수열 2,3,4,5 + 복습

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

#include<bits/stdc++.h>

using namespace std;

vector<int>arr;

int main() {
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (arr.empty()) {
			arr.push_back(x);
		}
		else {
			if (lower_bound(arr.begin(), arr.end(), x) == arr.end()) {
				arr.push_back(x);
			}
			else {
				arr[lower_bound(arr.begin(), arr.end(), x) - arr.begin()] = x;
			}
		}
			
	}
	cout << arr.size();
}

골드 2 이진탐색 문제입니다.

예전에 다른방식의 O(N^2)로 풀다가 실패한 문제.

 

 

lower_bound를 이용해서 O(NlogN)으로 풀 수 있다.

https://23dotory.tistory.com/24

12015번_가장 긴 증가하는 부분 수열2 / 가장 긴 증가하는 부분 수열3_BOJ

lower_bound를 사용할 생각을 못했음..

 

lower_bound(arr.begin(),arr.end(),k) => k와 같거나 보다 큰 첫번째 요소의 이터레이터 반환

upper_bound(arr.begin(),arr.end(),k) => k보다 큰 첫번째 요소의 이터레이터 반환

 

이터레이터가 arr.end()가 나올경우, push해주고 아닌경우 최적의 자리에 삽입해준다.

 

결론부터 이야기했지만 최적의 자리에 삽입한다는게 이 문제의 핵심이었다

최적의 자리를 찾는방법 중 하나가  lower_bound를 사용하는 것이고, 

이분탐색을 통해 자리를 찾을 수도 있다.

 

#include<bits/stdc++.h>

using namespace std;

vector<int>arr;

int main() {
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (arr.empty()) {
			arr.push_back(x);
		}
		else {
			int le = 0, ri = arr.size() - 1;
			int mid = (le + ri) / 2;
			int idx = -1;
			while (1) {
				if (le > ri) {
					break;
				}
				if (arr[mid] >= x) {
					idx = mid;
					ri = mid - 1;
					mid = (le + ri) / 2;
				}
				if (arr[mid] < x) {
					le = mid + 1;
					mid = (le + ri) / 2;
				}	
			}
			if (idx == -1)arr.push_back(x);
			else
				arr[idx] = x;
		}
	}
	cout << arr.size();
}

 

lower_bound 대신 이분탐색을 사용해 제출한 코드.

============================================================================================

23.2.16

 

이진탐색과 이진탐색기반의 lower_bound를 사용하면 O(N logN)만에 길이를 구할 수 있습니다.

하지만 그때 사용되는 배열로는 정확히 무슨 배열이 가장 긴 증가하는 부분수열을 알 수 없습니다.

 

따라서 후처리를통해 처리를 해주어야합니다.

 

8 14 9  17 2 15 16

이 배열을 lower bound를 이용해서 배열에 집어 넣을때, k번째 숫자가 n번째 자리에 들어간다고 하면

아래와 같이 표를 작성할 수 있습니다.

 

위는 K, 아래는 N입니다.

8	14	9	17	2	15	16
1	2	2	3	1	3	4

 

맨 뒤 인덱스부터 접근하여, 처음으로 Len 값에 접근하는 숫자부터 배열에 저장하면 됩니다. 그리고 Len-=1 합니다.

 

1.처음에 16을 발견합니다 (4)

2. 다음으로 15를 발견합니다 (3)

3. 2는 탈락합니다(1이므로, 2를찾아야합니다)

4. 17은 탈락합니다(3이므로)

5. 9를 발견합니다(2)

6. 14는 탈락합니다(2이므로 1을 찾아야합니다)

7. 8을 발견합니다(1)

 

역순으로 정리하면 8 9 15 16으로 정답입니다.