가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)가장 긴 증가하는 부분 수열은 주어진 배열에서 순서를 유지한 채로 길이가 가장 긴 증가하는 부분 수열을 찾는 문제이다. 예를 들면 배열 [10, 9, 2, 5, 3, 7, 101, 18]이 주어지면 이 배열에서 길이가 가장 긴 증가하는 부분 수열은 [2, 3, 7, 101]이며 길이는 4이다. 간단해 보이는데, 접근 방법을 모르면 어려운 유형이므로 기록한다. 해결 방법해결 방법은 2가지가 있다. 동적 계획법을 이용한 방법과 이분 탐색을 활용한 방법이다. 동적 계획법, 시간복잡도 O(N^2)#include using namespace std;int n,a[1003],cnt[1003],res;int main() { ..
가장 긴 증가하는 부분 수열
코드#include using namespace std;int n, a[1003], cnt[1003],res;int main() { cin >> n; fill(cnt, cnt + 1003, 1); for(int i = 0; i > a[i]; } for(int i = 0; i O(N^2)으로 가장 긴 증가하는 부분 수열(LIS, longest increasing subsequence)를 구하는 문제.
