https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 풀이 LIS(LDS) 풀이는 3가지다. 1. 완전탐색으로 푸는경우 => 시간복잡도 O(n^3) 2. DP => O(N^2) 3. 이진탐색 => O(nlongn) 완전탐색인 경우 for문을 이용한 단순 반복이므로 생략 DP로 접근 할 경우 , 부분 중복 되는부분을 찾아 최적화 시켜야한다. 2중 for문( 바깥쪽 i , ..
