가장 긴 증가하는 부분 수열 2 (LIS)

문제 해설 및 주의사항

수열 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)

 

풀이

0. A의 크기

- 최대 1,000,000 이다. 브루트 포스는 절대 불가능하다.

 

1. dp? 그리디 알고리즘 (dp 와 그리디 알고리즘의 명확한 구분은 무엇일까)

- 핵심은, 지금 인덱스 이전의 인덱스들 중 하한을 찾아내는 것이다. 하한을 찾아낸 뒤에,

하한이 없다면 현재 인덱스가 지금까지의 가장 큰 값이므로, LIS 배열에 push_back 해주면 된다.

하한이 있다면, 하한의 자리에 현재 인덱스 값을 넣어준다.

 

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
// 12019 가장 긴 증가하는 부분 수열 2

int main(){
	int n;
	cin >> n;
	
	vector<int> LIS;
	
	// i 번째 인덱스 까지만 있다고 생각하였을 때, 그때의 LIS 를 구하여 LIS 에 저장한다.
	for(int i = 0 ; i < n; i++) {
		int num;
		scanf("%d", &num);
		
		// LIS 에서 num 의 하한(값 이상이 처음 나오는 것)을 찾는다.
		auto iter = lower_bound(LIS.begin(), LIS.end(), num);
		
		// 하한이 존재하지 않는다면(지금 num 값이 가장 큰 값이라면)
		if(iter == LIS.end()){
			LIS.push_back(num);
		}
		// 하한이 존재한다면, 하한의 위치 값을 지금 num 값으로 바꾸어준다.
		else{
			*iter = num;
		}
	}
	cout << LIS.size() << endl;
	
}

 

---

퇴고