BOJ - 12015 가장 긴 증가하는 부분 수열 2 해결 전략 (C++)

• 문제 링크
  백준 12015번 - 가장 긴 증가하는 부분 수열 2

해결 전략

  본 문제는 BOJ에서 상당히 유명한 문제 유형인 LIS(Longest Increasing Sequence)의 두 번째 문제이다. 기본 LIS 문제들은 두 가지 타입으로 풀이법이 나뉜다. 문제 조건에 의해 구분되는데, 하나는 Dynamic Programming을 이용한 유형, 또 다른 하나는 Binary Search(Logarthmic Search Algorithm)를 이용한 유형이다. 이 문제는 후자에 속한다.

  허나, 익히 알려진 이 두 방법을 잠시 차치하고, 문제에 원론적으로 접근해보자. 그래야 이 문제를 풀 수 있으며, 앞으로 다른 문제들도 해결할 힘을 기를 수 있을 것이다. 한 가지 예시를 들어보자.

10 20 30 15 20 25 50 45 55 60

  이란 수열이 있다고 해보자. LIS를 어떻게 찾을 수 있을까?

가장 직관적인 방법을 생각해보자.

"10 20 30은 명확한데,,"
"10 15 20 25도 가능해보이네,,,"
"이어서 45 55 60을 붙이면 되겠네,,"
"그러면, 10 15 20 25 45 55 60이 답이겠네?"

~> 대부분, 직관적으로 LIS를 찾을 때 위와 같은 사고를 거쳐서 찾을 것이다.
=> 이 방법은 결코 잘못되지 않았다!!!

위와 같은 직관적인 사고 흐름은 본 문제 해결 Idea 도출의 시작이다!

'직관'에서 규칙성만 찾으면 되는 것이다.

  허나, 이 문제가 어려운 이유는, 그 '직관 속의 규칙'을 찾기가 어렵기 때문이다. PS 사고 방식이 익숙치 않은 대부분은 사람들(본인 포함)은 핵심 Idea를 단번에 뽑아내기 어려울 것이다. 그 Idea는 다음과 같다.

• 수열의 처음부터 Linear하게 훑는다. 최초 원소를 LIS 수열에 포함시킨다.

  • LIS: 10

• 증가하는 수열을 만들기 때문에, 다음 원소부터, LIS 수열의 마지막 원소보다 큰 원소일 경우 계속 삽입한다.

  • LIS: 10 20 30

• 다음 훑는 원소가 LIS 수열의 마지막 원소보다 작은 경우, LIS 수열을 이루는 원소 중 탐색 원소와 '가장 차이가 안나면서 더 큰' 원소를 찾는다.

• 이어서, 그 원소를 탐색 원소로 대체한다.

  • LIS: 10 15 30
    • 이 이유는 무엇인가? 이렇게 뒤죽박죽 섞이는 것이 말이 되는가?!
      • 말이 된다!

        • "우리는 현재 LIS 구성 상태에 관심있는 것이 아니라, 그 길이에 관심이 있다. 즉, 이 '대체'는 '현재까지의 LIS 길이를 보전하면서, 동시에, 미래의 새로운 LIS가 생기는 것을 대비하기 위함이다. 어떻게 대비를 하냐고? 예시를 이어서 보자."

• 위 원리를 토대로 계속 훑는다.

  • LIS: 10 15 20 (여기까진 기존 LIS 길이를 보전. 동시에 새 LIS도 구축 중)
  • LIS: 10 15 20 25 (새로운 LIS로 대체되었다)
  • LIS: 10 15 20 25 50
  • LIS: 10 15 20 25 45
  • LIS: 10 15 20 25 45 55
  • LIS: 10 15 20 25 45 55 60 (완성)

~> 이 원리가, 항상 적용될 것임은 증명이 없어도 직관적으로 이해할 수 있을 것이다. 이것이 바로 본 문제의 해결 Idea이다.
=> 이때, 여기서 "다음 훑는 원소가 LIS 수열의 마지막 원소보다 작은 경우, LIS 수열을 이루는 원소 중 탐색 원소와 '가장 차이가 안나면서 더 큰' 원소를 찾는다."라는 Rule을 실현하는 과정에 있어서 Logarithmic Search가 이용될 수 있는 것이다.
--> 그 중 가장 구현이 간단한 Binary Search를 적용하면 된다. 왜냐? LIS는 이미 Sorted이므로 Binary Search 적용이 가능하다! ★

  이처럼, '직관 속에서 규칙 찾기'를 통해 핵심 Idea를 도출할 수 있다. 그 Idea의 구현 과정에서 필요한 Search Algorithm을 선택하는 것 역시 중요한 센스이다. 이 문제는 잘 기억하도록 하자.

  아래는 정답 코드이다.

#include <iostream>
#include <vector>
// BOJ - 12015 LIS 2
using namespace std;

vector<int> a, ans;

int idx_bsearch(int k) {
	int lo = 0, hi = ans.size() - 1, mid;

	while (lo < hi) {
		mid = lo + (hi - lo) / 2;

		if (ans[mid] >= k) 
			hi = mid;
		else lo = mid + 1;
	}

	return hi;
}

int main(void) {
	int n, t, idx;

	cin >> n;
	for (int i = 0; i < n; i++) 
	{ cin >> t;  a.push_back(t); }
	ans.push_back(a.front());

	for (int i = 1; i < n; i++) {
		if (a[i] > ans.back())
			ans.push_back(a[i]);
		else {
			idx = idx_bsearch(a[i]);
			ans[idx] = a[i];
		}
	}
	cout << ans.size();

	return 0;
}