[C++] 알고스팟/동적계획법 - Longest Increasing Sequence
문제 링크
https://algospot.com/judge/problem/read/LIS
algospot.com :: LIS
Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다.
algospot.com
동일한 문제가 백준에도 있지만 종만북에서는 이 문제를 동적계획법과 이분법으로 해결하는 두가지 방법을 설명합니다.
먼저 이분법 방식부터 살펴보면
먼저 입력으로 주어진 길이와 동일한 빈 배열 c를 만들어줍니다.
그리고 a의 첫번째 값부터 시작하여 c에 아무 값이 없거나 가장 최근에 들어온 값이 a의 현재 위치의 값보다 작으면 c의 다음 빈칸에 넣어줍니다.
만약 a의 현재 값이 c의 마지막값보다 작다면 이분법으로 c에 있는 값 중 a의 현재 값보다 작은 가장 큰 값을 찾아내고 그 자리 바로 오른쪽 칸에 넣어줍니다.
이제 나머지 뒤의 값들도 위의 방법으로 동일하게 진행해줍니다.
a의 마지막 값을 넣었을 때 c에 최대 증가 순열이 저장됩니다.
DP로 푸는 방식은 배열의 처음부터 시작해서
현재값보다 다음값이 더 크면 다음값부터 시작되는 부분수열의 최대길이를 재귀탐색해 구하고 현재 길이에 더해주면 됩니다.
현재값보다 더 큰 다음값들이 여러개 나올 수 있기 때문에 모든 큰값들 위치에서의 부분수열 중 가장 길이가 긴 부분수열을 선택하면 됩니다.
구현 코드