[DP] LIS (최장 공통 부분 수열)
LIS (Longest Increasing Subsequence) 수열 안에 있는 증가 하는 부분 수열 중 가장 긴 것을 찾는 문제 Idea1 완전탐색입니다. 1) 수열을 처음부터 하나씩 증가하면서 (a[]의 모든 원소마다), 각 경우마다는 첫번째 수 a[i]를 정하고, 인덱스를 1씩 늘려가면서(a[i+1] ... ) 첫번째 수보다 큰 숫자들을 컨테이너(sub_a[])에 담습니다. 2) sub_a를 1)번 과정을 되풀이하는 재귀함수를 구현합니다. a[] = {3, 2, 1, 7, 5, 4, 2, 6} 첫번째 원소 3을 기준으로, 그 다음 가능한 7 5 4 6 중 다시 재귀적으로 LIS를 뽑습니다. #include #include using namespace std; /* LIS의 길이를 반환 */ int..
2019. 9. 6.
