최장증가수열

[C언어] LIS (Longest Increasing Subsequence) 최장 증가 수열 DP/binary search

LIS : 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분 수열. 부분수열의 각 수는 서로 연속할 필요는 없다 LIS 길이 구하기 : 가장 단순한 방법은 완전 탐색을 하는 것이다. 수열의 개수가 K개 -> 1개 이상의 원소를 갖는 부분 수열의 가짓수는 2^K 즉, 모든 부분 수열을 확인해 오름차순으로 정렬되어 있는지 확인하는 것은 매우 비효율적이다. 이를 개선하기 위해 다이나믹 프로그래밍으로 구현 가능하다. #1 DP(Dynamic Programming) 시간 복잡도 : O(n^2) 수열의 한 원소(k)에 대해, 그 원소에서 끝내는 최장 증가 수열 길이를 저장한다. => k를 제외한 모든 원소는 k보다 작아야 한다. 따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각..