해결 전략
본 문제는 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 30
-
위 원리를 토대로 계속 훑는다.
- 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;
}