Longest Increasing Sub-sequence Algorithm(LIS, 최장 증가 부분 수열 알고리즘)

Longest Increasing Sub-sequence Algorithm(LIS) 동적계획법(DP)문제를 풀다가 우연찮게 해당 알고리즘의 문제를 풀게되면서 이전 기억을 살려 다시한번 정리를 해보려고 한다. 해당 문제는 최장길이만 구하다 보니 동적계획법을 이용해서 해결이 되었지만, 더 다양한 문제를 해결하기 위해 그리고 LIS알고리즘을 더 잘 이해하기 위해 해당 페이지에 정리를 하려고 합니다. 정의(Definition) 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘 부분 수열은 연속적이거나 유일한 필요가 없다. 최장길이를 구하거나, 해당 부분수열을 구할 수 있다. 여러 시간복잡도로 문제를 해결할 수 있다. 부분수열이란? 주어진 수열에서 특정 원소들을 선택해서 만들어진 수열을 그 수..