최장증가수열
백준 11053: 가장 긴 증가하는 부분 수열 해설- python
✏️ 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✏️ 풀이 LIS(Longest Increasing Subsequence)라는 유명한 DP문제이다.만약 A={6, 2, 5, 1, 7, 4, 8, 3} 가 있을때 LIS는 {2, 5, 7, 8}이 된다. 증가하는 수열은 {2, 5}, {2, 7} 등 많지만 그 중 가장 긴 것이 LIS가 된다. - dp[i]를 전부 1로 초기화했다. LIS의 길이는 기본적으로 1은 될 것이기 ..