배움과 성장/알고리즘·문제풀이
백준 12015 Java: LIS 길이를 Lower Bound로 O(N log N)에 구하기
백준 12015를 풀던 2022년 5월에는 이진 탐색에 심리적인 거부감이 있었다. 반나절 정도 접근을 고민한 뒤 list를 이용한 풀이를 찾아봤고, 그대로 끝내지 않고 array 방식으로 다시 구현했다. 당시 제출에서는 list 풀이가 756ms, array 풀이가 592ms였지만 한 번의 채점 결과를 일반적인 성능 benchmark로 보지는 않는다.이 문제에서 가져갈 핵심은 각 길이의 증가 부분 수열이 가질 수 있는 가장 작은 마지막 값을 tails에 유지하는 것이다.tails의 의미tails[i]를 길이가 i + 1인 strictly increasing subsequence 중 현재까지 찾은 최소 마지막 값이라고 정의한다.새 값 value가 들어오면 다음 두 경우다.value가 현재 모든 tail보다..