[SW 문제해결 응용] LIS :: 최장 부분 증가 수열
LIS(Longest Increasing Subsequence) 최장 부분 증가 수열 구하는 문제 : 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제 부분 수열에 포함되는 요소들이 순서상 연속적일 필요는 없음 문제 풀이를 위한 방법으로 3가지가 있다. 1. 완전 탐색2. 다이나믹 프로그래밍3. 이분 탐색 완전탐색, O(2^N) 완전 검색 적용 1. 수열의 모든 부분 집합을 구하여 각 부분 집합이 증가 수열이 되는지 판별 2. 증가 수열이 되는 수열 중 가장 길이가 긴 수열을 찾음 ex)S = {3, 2, 6, 4, 5, 1} 2^6 = 64개의 부분집합 길이가, 0일 때, {}1일 때, {3}, {2}, {6}, {4..
