오늘은 유명한 유형 중 하나인 LIS 유형에 대해 정리해보고자 한다. 해당 유형을 안 지 얼마 되지 않았지만, 유형이 어느정도 정형화 되어있는 느낌이다. 해당 유형을 풀이하는 방법은 DP, 이분탐색 2가지가 있다. DP로 풀이할 경우 O(N^2)의 시간복잡도를, 이분탐색으로 풀이할 경우 O(NlogN)의 시간복잡도를 가진다. 따라서 문제에 나와있는 조건을 잘 보고 시간복잡도를 따져서 알고리즘을 선택하는 것이 중요하다. 해당 유형은 가장 긴 증가하는 부분 수열의 길이까지만 구하거나, 더 나아가 부분 수열 자체를 출력해야하는 문제들이 있다. 해당 유형은 1,2편으로 나누어 작성하고자 하며, 해당 글(1편)에서는 가장 긴 증가하는 부분 수열의 길이까지만 구하는 문제를 다뤄보고자 한다. 우선 백준 12015번 ..
