BOJ 2352 반도체 설계 - lis, lowerbound, upperbound

lower, upper bound,
lis logN...-> 이유까지...
팬윅 트리도 공부해볼까..

Longest Increasing Subsequence (가장 긴 증가 부분수열), 줄여서 LIS를 구하는 문제이다.
KOI 지역본선 초등부 문제 중에서 '전봇대'라는 문제와 매우 비슷하다.

LIS는 dp로 풀어왔었고, 그 경우 시간 복잡도는 O(N^2) 이었다. 이 반도체 설계라는 문제는 N이 40000이라... N^2 의 알고리즘으로는 TLE(Time Limit Exceeded)를 받는다.

다행히 NlogN의 알고리즘을 잘 정리해 놓은 블로그가 있었다!
http://dyngina.tistory.com/16


4 2 6 3 1 5 라는 수열이 있다고 하자.

1. 배열에 4가 들어간다. {4, }
2. 배열에 있는 4를 2로 바꾼다. {2, }
3. 배열에 6이 들어간다. {2, 6}
4. 배열에 있는 6을 3으로 바꾼다. {2, 3}
5. 배열에 있는 2를 1로 바꾼다. {1, 3}
6. 배열에 5 가 들어간다. {1, 3, 5}

배열의 길이인 3이 가장 긴 증가 부분수열의 길이이다.
이 방법의 경우 배열안의 값들은 가장 긴 증가 부분수열을 이루는 값들이 아닐 수 있다.

위의 블로그에 따르면, 배열에 들어가있는 값들의 의미는 이렇다.
예를 들어, 값 x가 배열에 들어가있다면, x를 마지막으로 포함하는 LIS의 길이가 x까지의 배열의 크기라는 것이다.
{1, 3, 5}를 보면 LIS를 구성하는 값이 1, 3, 5 라는 것이 아니라, 5를 마지막 수로 포함하는 LIS의 길이가 배열의 크기인 3이라는 것이다.

그리고 구하는 과정을 보면, 더 작은 값들로 바꿔지는 과정이 보이는데, 그래야 뒤에 올 수 있는 값 후보들을 최대로 해서 가능한 모든 경우를 다 볼 수 있다.

예를 들어 1, 3, 7, 5, .... 이렇게 있는데, {1, 3, }을 선택한 후 , 5를 선택하는 것이 7을 선택하는 것 이상의 답을 구할 수 있다.

이 방법이 greedy방법 같아보이는데...(여태 LIS는 dp로만 푸는 줄 알고 있었다.) 정확히는 모르겠다.

그런데, 여기서 하나 알아야 할 것이 lower bound이다. 위에서 새로 들어온 수로 바꿔주는 과정에서 바꿀 위치를 찾는 데 lower bound가 필요하다.

lower bound는 http://blog.naver.com/jwoo619/220704620584 이 곳에 잘 설명되어 있는데,
찾고자 하는 값 이상이 처음 나타나는 위치로 볼 수있고, 쓰고싶다면, 이분탐색을 이용해서 구현하거나, C++ STL에서 <algorithm>을 include하면 사용할 수 있다. 이 함수를 사용하면,
lower bound의 경우, val보다 작지 않은 값 즉, val이상의 값이 처음 나타나는 위치(index)를 가리키는 iterator를 반환해주는데, 모든 값이 val보다 작다면 제일 마지막 위치를 가리키는 iterator를 반환해준다.
참조 : http://www.cplusplus.com/reference/algorithm/lower_bound/
upper bound의 경우, val보다 큰 값이 처음 나타나는 위치(index)를 가리키는 iterator를 반환해준다.

1 1 1 2 2 2 3 3 3 이란 수열이 있고, val=2이면,
val의 lower bound는 2가 처음 나오는 index 3을, upper bound는 (2보다 큰)3이처음 나오는 index 6을 반환할 것이다. (index는 0부터 시작)

근데, 이렇게 써놓고 보니 lower bound대신 upper bound를 써도될 것 같은데...?
일단 코드를 짜봐야겠다.

해보니 upper_bound도 역시 된다! lower_bound를 써야하나, upper_bound를 써야하나..에대해서는 나중에 그런 고민을 할 문제가 나오면 고민해보도록 하자.
이제 이분탐색과, 그냥 linear(?)로 구현해보고 마무리해야겠다.

//추가 - linear(?)로 풀다가 생각난건데, 만약 가장 긴 감소하는 부분 수열을 구하는 것이라면, 물론LIS를 거꾸로 해도 되겠지만, LIS에서 val 이상이 처음 나타나는 위치를 찾아서 더 작은 값으로 바꿔주었다면, val 이하가 처음 나타나는 위치를 찾아서 더 큰 값으로 바꿔주는 식으로 하면 될 것 같다. lower bound 를 못쓰겠지만, 이분 탐색으로 하면 속도도 빠르게 할 수 있을 것이다.

//추가 - BOJ Slack에서 doju님의 관련 답변

lis와 상관없고 길이만을 구하기 위한 그 배열에 들어가있는 수의 의미는 x번째 숫자로 나올 수 있는 최솟값...!! 왜냐하면 최대길이를 구해야하니까, 그 위치에 올 수 있는 최소값이 들어가야한다! 음 나도 이해는 했지만 확실히, 완벽하게 이해한 것은 아니었던 것 같다.

마지막으로, 이 방법말고도 index tree를 이용하는 방법도 있다고 하는데, 그 방법의 경우 배열의 요소까지 구할 수 있다고 한다. 공부해봐야 겠다.