백준 12015번 가장 긴 증가하는 부분 수열 2

- 문제 설명

 

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

ex) A = {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이다. 길이는 4이다.

 

 

- 입력

 

첫째 줄에 수열 A의 크기 (1 <= N <= 1,000,000)둘째 줄에 수열 A를 이루고 있는 A_i가 주어진다. (1 <= A_i <= 1,000,000)

 

 

- 출력

 

수열 A의 가장 긴 증가하는 부분 수열의 길이 출력

 

 

* 문제 풀이의 핵심

 

1. 알고리즘 : 이분 탐색을 활용한 LIS 알고리즘

 

- 로직

 

1) LIS의 값을 저장할 벡터 생성 후, 수열 A의 첫 번째 값 삽입

 

2-1) 벡터의 끝 값 < 수열의 값 : 벡터에 수열 A의 값 삽입

 

2-2) 벡터의 끝 값 >= 수열의 값 : lower_bound (작은 값과 근접) 이분탐색을 통해서 해당 값이 벡터의 어떤 위치에 들어갈 수 있는지 검색 후, 벡터의 값 갱신

 

3) 정답 : 벡터의 길이

 

 

- 그림 설명

 

ex) A = {1,2,3,4,5}

 

 

 

 

※ 고려할 점

 

1. 이분탐색을 위해 수열 A를 정렬할 필요가 없다.

 

2. 벡터의 결과는 가장 긴 증가하는 부분 수열의 원소와 항상 동일하지는 않다.

 

3. 입력되는 수가 많기 때문에 입출력 가속을 사용하면 시간을 줄일 수 있다.

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

 

- 소스코드

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N;
int A[1000001];
vector<int> lis;

int find_lower_bound(int n) {	
	int left = 0;
	int right = lis.size() - 1;
	while (left < right) {
		int mid = (left + right) / 2;

		if (lis[mid] >= n) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}

	return left;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	int i;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	
	lis.push_back(A[0]);
	
	int l_idx = 0;
	for (i = 1; i < N; i++) {
		if (lis[l_idx] < A[i]) {
			lis.push_back(A[i]);
			l_idx += 1;
		}
		else {
			int idx = find_lower_bound(A[i]);
			lis[idx] = A[i];
		}
	}

	cout << lis.size() << "\n";
}

 

 

- 문제링크 : https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

 

- 제출한 코드

 

입출력 가속 사용 X

입출력 가속 사용 O

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요