백준 12015 가장 긴 증가하는 부분 수열 2, 백준 12015 가장 긴 증가하는 부분 수열 2 C/C++ 풀이 - Binary Search

백준에 엄청 자주 등장하는 증가하는 부분 수열 문제이다.

N이 1백만 scale 을 가지므로 최대 NlogN 안에 풀어야한다. 

그러므로 수열 순회는 N번 안에 종료해야하고 나머지 연산이 log N 안에 끝내야하므로 

Binary Search 를 적용하여 풀 수 있을 것으로 기대한다.

 

1. 문제 접근 

- 가장 긴 부분 수열을 만들기 위해 수열을 탐색하며 부분 수열을 지속적으로 갱신한다.

 

2. 문제 해결

- 가장 긴 수열의 정보를 지속적으로 갱신하며 진행하여 수열을 1번만 순회할 수 있도록 한다.

- 가장 긴 수열의 정보를 수정할 때, 수정할 위치를 찾는 것은 Binary Search를 이용하여 logN안에 수행한다.

 

가장 긴 증가하는 부분 수열 2 문제는 부분 수열의 값이 어떤 것인지 중요하지 않고,

총 갯수만을 요구하므로 몇 개인지만 정확하게 세주면 된다.

#include <cstdio> //#include <stdio.h> //C언어
//using namespace std; //C++

int arr[1000001];
int dp[1000001];
int N;
int lowerBound(int idx, int arrValue);
int solve();

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", arr + i);
	}
	printf("%d\n", solve());

}


int solve() {
	int idx = 0;//dp 에 저장할 인덱스
	//한 번 순회
	for (int i = 1; i <= N; i++) {
		 //dp의 현재 idx에 있는 숫자보다 클 경우 추가
		if (dp[idx] < arr[i]) {
			dp[++idx] = arr[i];
		}
		//아닐경우 arr[i]의 숫자보다 (같거나 큰 수 중 가장 앞에 있는 수)를 dp에서 찾아 교체 
		else {
			int idxChange = lowerBound(idx, arr[i]);
			dp[idxChange] = arr[i];
		}
	}
	return idx;
}

int lowerBound(int idx, int arrValue) {
	int s=0, m, e=idx;
	int ret = e;
	while (s <= e) {
		m = (s + e) / 2;
		//dp 값보다 같거나 작은 자리에 저장해야 증가하는 수열 가능
		if (dp[m] >= arrValue) {
			e = m-1;
			ret = m;
		}
		else {
			s = m + 1;
		}
	}
	return ret;
}

dp에는 부분수열을 저장하고, arr은 input값을 저장한다.

dp 는 idx라는 인덱스 번호로 접근할 것이고,

dp < arr 일 경우 idx 자리에 그 숫자를 추가한다.

dp >= arr 일 경우, 증가하는 수열을 유지하기 위해 arr 보다 크거나 같은 값을 찾아 dp 배열을 갱신해준다.

 

dp 배열에서 값을 찾을 때는 lowerBound 를 이용한 binary search 를 진행한다.

dp 배열에 넣을 수 있는 가장 앞의 수를 찾는 방법이다.

넣을 수 있는 가장 앞의 수부터 갱신해야 뒤의 배열에서 새롭게 갱신될 때 문제가 생기지 않는다.(증가하는 수열을 유지할 수 있다.)

---

위를 이용하면 가장 긴 증가하는 부분 수열 5 문제도 풀 수 있다.

2와 달라진점은, 수열 값의 범위가 -10억부터 10억으로 바뀐 것과, 

가장 긴 부분 수열이 될 수 있는 수열의 출력을 요구한다는 것이다.(가장 긴 수열은 여러 개가 될 수 있음)

 

tracking 정보를 저장하고 메모리를 줄이기 위해 vector를 사용했는데,

사실 배열 2개를 1,000,000개씩 할당받아서 구현해도 같으므로 C로도 구현할 수 있다.

 

수열 값이 1부터가 아니므로 dp값의 0번째 숫자는 -1000000000보다 작아야하므로 주의하자.

dp[0]값을 설정하지 않을 경우(0일 경우) 테스트케이스 2%에서 틀린다.

 

로직은 같지만 수열을 출력하기 위한 tracking 을 보자. 

dp의 몇 번째 인덱스에 저장되는지와 그 때의 수열 값을 저장하는 vector다.

이제 dp수열을 갱신할 때, tracking 에다가 그 정보를 모두 넣어준다.

모두 넣고 나면 N개가 되는데, 이를 뒤에서부터 순회하며 수열을 추적한다.

 

즉, 수열의 길이가 6이라면

6번째에 들어간 값을 tracking 배열에서 찾는다. 

뒤에서부터 하는 이유는 부분 수열에 들어간 순서가 중요하기 때문이다.

만약 5번째 들어간 수가 6번째 들어간 수보다 늦게 들어갔을 경우, 그 가장 긴 부분 수열이 아니므로 6부터 찾고,

그 전에 들어온 5번째 수를 찾는다.

 

printTrace()에서 하는 역할이 그것이다. 

뒤에서부터 순회하여 dp 배열을 갱신한다.

 

 

#include <cstdio>
#include <vector>
using namespace std;

int arr[1000001];
int dp[1000001];

vector <pair<int, int> > tracking;// dp 에 저장된 idx, value 저장

int N;
int lowerBound(int idx, int arrValue);
int solve();
void printTrace();

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", arr + i);
	}
	printTrace();
	return 0;
}


int solve() {
	int idx = 0;//dp 에 저장할 인덱스
	dp[0] = -1000000001; // 숫자 범위 -10억 ~10억
	//한 번 순회
	for (int i = 1; i <= N; i++) {
		 //dp의 현재 idx에 있는 숫자보다 클 경우 추가
		if (dp[idx] < arr[i]) {
			dp[++idx] = arr[i];
		//경로저장
			tracking.push_back(make_pair(idx, arr[i]));
		}
		//아닐경우 arr[i]의 숫자보다 (같거나 큰 수 중 가장 앞에 있는 수)를 dp에서 찾아 교체 
		else {
			int idxChange = lowerBound(idx, arr[i]);
			dp[idxChange] = arr[i];
		//경로저장
			tracking.push_back(make_pair(idxChange, arr[i]));
		}
	}
	return idx;
}

int lowerBound(int idx, int arrValue) {
	int s=0, m, e=idx;
	int ret = e;
	while (s <= e) {
		m = (s + e) / 2;
		//dp 값보다 같거나 작은 자리에 저장해야 증가하는 수열 가능
		if (dp[m] >= arrValue) {
			e = m-1;
			ret = m;
		}
		else {
			s = m + 1;
		}
	}
	return ret;
}

void printTrace() {
	int Num = solve();
	int idx = Num;
	printf("%d\n", Num);

	
	//tracking 된 정보 순회 -> dp배열 정정
	for (int i = tracking.size()-1; i >= 0; i--) {
		//갱신된 순서 맞는지 확인 -> 5자리에 저장된 것은 4자리에 저장된 것보다 늦게 저장되어야함
		if (tracking[i].first == idx) {
			dp[idx--] = tracking[i].second;
		}
	}
	for (int i = 1; i <= Num; i++) {
		printf("%d ", dp[i]);
	}

}