kwakmu18

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 가장 긴 증가하는 부분 수열(LIS)라고 한다. \( O(N^2) \) 알고리즘 배열의 i번째 값으로 끝나는 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 저장한다. dp[i]...