문제 백준 14002 가장 긴 증가하는 부분 수열 4 C++ 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 LIS 구하기의 경우 DP로 해결하면 O(N^2)의 시간복잡도를 가집니다. N = 1000이므로 DP로도 해결가능해 DP로 풀었습니다. N이 더 커진다면 이분 탐색을 활용해야 합니다. 최장 증가 부분 수열의 경로도 출력해줘야하는데, 부모를 설정하면 경로를 쉽게 표시할 수 있습니다. 소스 코드 1 2 3 4 5 6 7 ..