lis1 [알고리즘 정리] 최장 증가 수열(LIS,Largest Increasing Sequence) 알고리즘 최장 증가 수열이란 주어진 수열의 부분수열중 가장 긴 증가 하는 수열을 말합니다. 예를들어, 다음과 같은 10개 원소의 수열에서 1, 3, 4, 5, 6, 9, 10의 7의 부분 수열이 가장 긴 증가 하는 수열입니다. DP를 사용한 아이디어로서, 이분탐색을 이용하여 O(NlogN)의 시간복잡도로 해결합니다. 앞에서 부터 뒤로 O(N)으로 탐색을 하고 현재 원소의 놓여질 최적의 자리를 찾는데 이분탐색을 이용하여 O(logN)이 걸립니다. 1. 처음 벡터에 -INF를 넣어줍니다. 2. 벡터의 맨 뒤의 값보다 넣으려는 1이 크기 때문에(-INF 2018. 7. 16. 이전 1 다음
