알고리즘 - LIS(가장 긴 증가하는 부분 수열)
1. 개요 LIS는 Longest Increasing Sequence의 약자로 특정 값들이 저장되어 있는 배열 형태에서 순차적으로 증가하는 부분 수열 중 가장 길이가 긴 것을 의미한다. 예를 들어, 현재 아래와 같은 배열이 있다고 가정하자. 인덱스 i 0 1 2 3 4 5 6 7 8 arr[i] 10 20 40 30 1 3 5 2 90 여기서 가장 긴 증가하는 부분 수열, 즉 LIS는 어떤 것이 있을까? 우선 각 숫자가 이전의 수보다 크다면, 그 순서가 가장 큰 경우를 구해보자. 그 배열을 sequence의 약자인 seq라고 해보자. 우선 i = 0 인 arr[0] = 10 일 때, 자기 자신 혼자 있더라도 수열을 만들 수 있으며 혼자서라도 LIS의 일부가 될 수 있으니 1로 시작할 수 있다. arr[1..