lis

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 다음 조건을 만족하는 수열이다.각 원소가 이전 원소보다 크다. (증가하고 있다)그 길이가 최대이다 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이다. 구현 방법DP를 이용한 방법이분탐색을 이용한 방법 DP를 이용한 방법 알고리즘 설명간단하지만 시간복잡도가 O(n^2)로 이분탐색보다는 큰 알고리즘이다dp[i]:  i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이라고 한다면,주어진 배열에서 인덱스를 한 칸씩(i+=1) 늘려가면서 확인합니다.내부 반복문으로 i보다 작은 인덱스들을..