LIS와 유사한 문제, 다양한 방법으로 해결할 수 있다. #include #include #include using namespace std; int a[100001], exist[1000001], N; int binary_search(int start, int end, int element) { while (start a[mid]) start = mid + 1; else end = mid; } if(a[end]==element) return end; else return -1; } int main(void) { cin >> N; for(int i=0; i> a[i]; sort(a, a+N); for(int i=..
LIS 알고리즘을 사용하면 간단하게 해결할 수 있다. #include using namespace std; int a[1000], length[1000], n; void dpFunc() { int res=0; for(int i=0; ires) res=length[i]; } cout > n; for(int i=0; i> a[i]; dpFunc(); return 0; }
🧐 최장 증가 부분 수열 (LIS)란? 최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.) 아래의 예시 수열을 보자. [ 7, 3, 5, 2, 7, 4, 8, 2] 이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다. 📝 LIS를 구해보자 LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다. 1) 동적 계획법 (Dynam..
