LIS

문제 https://www.acmicpc.net/problem/14003 풀이 LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11053)부터 차례대로 풀면 어느새 여기까지 풀게 된다. 이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 LIS를 직접 출력해야 하는 문제가 이 문제이다. 원래는 Swift로 작성하려 했지만, 백준의 입력시간 문제 때문에 Swift론 입력 횟수가 적은 O(n²)문제를 풀고 O(nlogn) 문제는 C++로 작성하였다. 기본적인 알고리즘 콘셉트는 다음과 같다. ...