문제 링크 : https://www.acmicpc.net/problem/12015 LIS는 최장 증가 부분 수열을 의미한다. 주어진 수열에서 숫자를 몇개 빼서 가장 긴 증가 수열을 만드는 것이 규칙이다. [0, 1, 2, 0, 5, 4]에 대해서 LIS를 찾는다고 하면, [0, 1, 2, 5] 또는 [0, 1, 2, 4]가 답이다. 부분 수열이 인덱스 i에서 끝날 때의 LIS 수열의 길이를 lis[i]라고 할 때, lis[i]에 대한 점화식을 적용하면 O(N^2) 해법을 쉽게 떠올릴 수 있다.def dp(arr): N = len(arr) lis = [1] * N for i in range(N): # 0부터 i까지 구간에서 부분수열의 최대 길이를 구한다. for k in ran..