백준 12015번: 가장 긴 증가하는 부분 수열 2

✔ 풀이를 위한 아이디어

• Dynamic Programming 중 특별케이스인 LIS (Longest increasing Subsequence)
• bisect 표준 라이브러리를 활용한 이분 탐색 (Binary Search)
  
  

✔ 코드

import sys
from bisect import bisect_left

n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
lis = []

for n in nums:
    if not lis:
        lis.append(n)
        continue
    if lis[-1] < n:
        lis.append(n)
    else:
        index = bisect_left(lis, n)
        lis[index] = n

print(len(lis))

• 이전에 풀었던 '가장 긴 증가하는 부분 수열' 문제와 크게 다른 점이 없어보였기 때문에 겁없이 도전했다. 하지만, N과 수열을 구성하는 요소들의 범위가 크게 달라진 것은 알고리즘 또한 완전히 변화해야 함을 의미했다.
• 풀이 방법이 도저히 떠오르지 않아, https://jason9319.tistory.com/113 에서 LIS라는 케이스에 대해서 공부하였다. 이전의 방식이 O(N^2)의 시간복잡도를 가지고 있었다면, 이 방식은 O(NlogN)만에 가장 긴 증가하는 수열의 길이를 찾아낼 수 있다.
• 이를 구현하기 위해서는 증가하는 숫자를 고르며 추가해나가되, 맨 끝 값보다 작은 수가 나타난다면 수열의 규칙성을 깨지 않는 위치를 탐색해 그 수로 대체해버려야 한다.
• 이 위치를 탐색 할 때, 이분 탐색 (Binary Search) 이 활용되며, 나는 Python의 bisect 모듈을 활용하여 구현하였다.
• 한가지 주의할 점은 lis에 담긴 수열이 실제 최장 수열은 아니라는 점이다. (삽입된 값이 실제로는 뒤에 있을 수도 있으므로) 다만, 최대한 작은 값들로 대체하면서 원래라면 추가하지 않았을 값들도 추가하게 되므로 최장 수열의 길이는 구할 수 있다.
  
  

내가 풀기엔 너무 이른 문제였던 것 같다. 다음에 꼭 복습하도록 하자!

✔ 관련 개념

• Dynamic Programming 중 특별케이스인 LIS 와 bisect를 활용한 O(logN)의 이분탐색 구현