소개 수열의 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크면서, 가장 긴 길이를 가지는 부분 수열을 찾는 알고리즘 DP 방식과 Binary Search를 쓰는 Greedy 방식 두 가지가 있으며, 별개의 방식이 아닌 두 방식이 밀접하게 연관되어 있다. 아이디어 LIS는 현재까지 구한 부분 수열의 결과를 이용해 더 긴 부분 수열을 만들어 나가는 문제이다. DP는 이전 계산 결과를 이용해 현재 상태를 구하며, Binary Search를 이용한 방식은 같은 아이디어를 유지하면서 탐색 과정을 최적화한 것이다. ...
문제 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++로 작성하였다. 기본적인 알고리즘 콘셉트는 다음과 같다. ...