lis 알고리즘 : lower_bound 이용해서 그리디하게 해결해 봅시다.

 lis 알고리즘은, 최장 증가 수열을 구하는 알고리즘입니다. 길이가 n인 수열이 있을 때, 이것을 O(nlogn)에 구할 수 있는 방법은 일종의 그리디를 이용한 것입니다. 물론, 조금 더 어려운 응용 문제를 풀기 위해서는 세그먼트 트리라는 자료구조를 알아야 하지만, 여기에서는 논외로 하도록 하겠습니다.

 

---

 먼저 전체 소스 코드를 보겠습니다.

 

 res는 최장 증가 수열의 길이를 구하기 위한 벡터입니다. v는 문제에 주어진 수열입니다. 문제에 주어진 수열 전체를 돌면서, 먼저 lo 값을 구하고 있습니다. 이 lo 값은 res에서 v[i]보다 크거나 같은 최초의 위치를 찾습니다. 그 위치가 res의 크기와 같다면, res의 뒤에 추가합니다. 그렇지 않다면, res[lo]값에 v[i]를 갱신합니다.

 

 일단 전체 시간 복잡도는 어렵지 않습니다. 수열의 크기가 n이라면, O(nlogn)입니다. 왜냐하면, lower_bound가 정렬된 배열에서는, O(logn)만에 수행되기 때문입니다. 처음 수행될 때 res 배열에는 아무것도 없으니까 log(n)보다 빠르게 수행되는 것이 아니냐고 반문하실 수 있습니다. 실제로 저에게 왔던 질문입니다.

 

 

 좋은 질문입니다. 이렇게 생각해 봅시다. n/2개만큼 돌렸을 때, res 배열에 n/2개만큼이 들어갔다. 나머지 n/2개를 볼 때 최악의 경우에 res 크기의 log, 그러니까 밑이 2인 log(n/2)만큼 수행이 될 겁니다. 이는 (밑이 2인 logn - 밑이 2인 log2)로 바꿀 수 있습니다. 이것을 n/2회 수행합니다. 앞에 상수는 무시하니까, 결국 O(nlogn)이 됩니다. 이제 4줄짜리 알고리즘을 설명해 보도록 하겠습니다. 정당성 증명은 무리수인 거 같긴 합니다.

 

---

 먼저, 17번째 줄의 의미를 다시 보겠습니다.

 

 현재 res에 이런 식으로 저장이 되어 있다고 해 보겠습니다. 즉, 1번째 원소부터 k번째 원소까지 보았을 때, 최장 증가 수열의 길이가 x였다고 해 보겠습니다. 위 그림에서 x의 값은 4입니다. 이 상황에서, k+1번째 원소가 res[x-1]보다 크다고 해 보겠습니다. 예를 들어 27이였다고 해 보겠습니다.

 

 그러면 단순히 뒤에 추가해 주면 됩니다. 그리고, 이것은 단순히 뒤에 추가된 것이 아닙니다. for loop가 0부터 (int)v.size()-1 까지 돕니다. i가 계속 증가하는 상황입니다.

 

 그러면 i번째 원소가 res의 back에 추가되기 전에 res에는 i보다 작은 위치에 있었던 값들이 차례대로 들어있었을 겁니다. 심지어, 맨 뒤에 있는 값도 i보다 작은 위치에 있었던 원소일 겁니다. 순서를 바꾸지 않고 뽑는다는 조건에 맞는 셈입니다. 역으로 말했을 때, i번째까지 뽑았을 때, res의 크기가 x였다는 것은 길이 x의 부분 증가 수열을 만들 수 있다는 것을 의미합니다.

 

 왜냐하면, i번째 원소를 넣기 전에 res는, i번째 원소를 뽑기 전의 원소들이 들어가 있을 겁니다. 군청색으로 칠한 것 중 맨 마지막에 있는 원소가 벡터 v에서 i'번째 원소를 뽑은 것이라고 해 보겠습니다. 그러면 i'는 i보다 작을 수 밖에 없을 겁니다.

 

 

 

 역시 마찬가지입니다. 보라색, 그러니까 i'번째 원소를 추가하기 전에 이미 [0, ... , i'-1]번째까지 고려한 정보가 들어가 있습니다. 이런 식으로 계속 귀납적으로 들어가다 보면, res의 크기가 x일 때, 길이가 x인 lis를 만들 수 있다는 결론을 내릴 수 있어요.

 

 문제는 19번째 줄 else에 걸려있는 부분입니다. 이것을 어떻게 해석하면 좋을까요? 일단 이런 식으로 lis가 들어왔을 때, 전체 수열은 <1, ... , 2, ... , 13, ... , 25, ... , 27, ... > 이런 식으로 구성이 되어 있을 겁니다. 그 다음에 10이 들어왔다. 그러면 입력으로 들어온 수열은, <1, ... , 2, ... , 13, ... , 25, ... , 27, 10, ... > 이렇게 구성이 되어 있다는 것을 알 수 있습니다.

 

 그 때, res[lo]에 v[i]의 값인 10을 넣는다고 했습니다. lo는 res에서 10보다 크거나 같은 원소가 있는 최초의 위치를 의미합니다. 봤더니, 2번째 위치에 있는 13부터 그러네요. 따라서 이 값을 13에서 10으로 바꿉니다.

 

 

 위와 같이요. 그러면 lis의 값은 5이지만, res[2]의 값이 13에서 10으로 바뀌었습니다. 이는 상당히 중요한 의미를 가집니다. 왜냐하면, 그 다음에 11, 12, 13이 차례대로 나왔다고 한다면 아래와 같이 res가 구축될 수 있기 때문입니다.

 

 

 어떻게 된 일일까요? 일단 res는 항상 sorting 되어 있는 상태임은 자명해 보입니다. 왜 그런지는 부등식을 이용하면 쉽게 prove가 가능하니 생략하도록 하겠습니다.

 

---

 이렇게 생각해 보겠습니다.

 lo번째 위치를 군청색으로 표시했습니다. 군청색의 위치가 v의 i번째에 있는 원소로 대치됩니다. 이 때 한 가지 확실한 것은 i번째로 대치된 위치 전에, i번째 전 위치에 있었던 원소가 들어가 있다는 것입니다. 그렇지 않다고 하면, i번째보다 우측에 있는 원소를 탐색했어야 했는데, 14번째 줄에 있는 for loop를 보면 그렇지 않습니다.

 

 그런데, 잘 보시면 lower_bound입니다.

 

 더 정확히 보면, else문에 걸렸을 때, res[lo]를 v[i]로 업데이트 하기 전에, res[lo]의 값은 v[i]보다 크거나 같습니다. 그런데, 이 res[lo]의 값을 v[i]로 업데이트 했단 말이죠. 이건 또 무엇을 의미할까요? 예를 들어보겠습니다. res에 37이 있었던 곳에 25를 넣는다. 아래 그림을 보겠습니다.

 

 

 당연하게도 23 전에 있었던 것들은 23보다 작고, 37 이후에 있는 것들은 37보다 클 겁니다. 이는, 군청색 위치가 37일 때 보다 25일 때, 군청색 바로 뒤에 들어갈 수 있는 후보해가 더 많이 생기기 때문입니다. 예를 들어서, 25 다음에 28이 들어왔다고 해 보겠습니다. 만약에, 37이 들어갔다면 28은 어디로 들어가야 할까요? 37 뒤에 들어갈 수 있나요?

 

 

 그렇지 않습니다. 기존에 37의 뒤에 있었던 값들은 37보다 컸을 겁니다. 하지만, 25로 바꾸었을 때에는 어떤가요?

 

 

 무난하게 뒤에 들어갈 수 있습니다. 심지어 그 뒤에 올 수 있는 후보 값들의 집합도 늘려놓을 수 있습니다. 뒤에 오는 경우를 모두 고려해 보았을 때, 현명한 선택임을 알 수 있습니다. 만약에, 23, 37, ... 이렇게 이어지는 경우가 23, 25, ... 로 이어지는 경우보다 최선의 선택이였다고 가정해 봅시다. 23, 37 을 포함하는 최선의 선택지 후보가 아래와 같다고 해 보겠습니다.

 

 

 그런데, 사실 이것은 군청색 부분을 25로 만들어도 가능합니다. 왜냐하면 t1>37이라면 t1>25이기 때문입니다.

 

 

이런 그리디 유형 어디선가 많이 설명 드렸던 거 같은데, 잘 찾아보면 옛날 유사코에 많이 보이던 것입니다. 알아두시면 나름 유용하게 써먹을 일이 있을 거에요. 여기서 질문. lis의 답을 출력해 봅시다. res에 있는 것을 그대로 출력하면 될까요? 그렇지 않다면 어떻게 하면 좋을까요?