가장 긴 증가하는 부분 수열51 [백준]BOJ 11053 - 가장 긴 증가하는 부분 수열 5 - C++/DP https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)www.acmicpc.net LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11722)부터 차례대로 풀면 어느새 여기까지 풀게 된다.이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 .. 2023. 3. 1. 이전 1 다음
