DP로 생각하기 - LIS 문제와 그 응용
Longest Increasing Subsequence (LIS)최장 부분 증가수열 문제는 DP 문제의 대표적인 문제 중 하나다. 먼저, 문제부터 보자.※ 문제 출저 (인프런 강의 - 파이썬 알고리즘 문제풀이 입문) 문제N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는 원소들의 집합의 길이를 구하라. 입력)5 3 7 8 6 2 9 4 출력)4 DP의 조건에 해당하는가이 문제가 DP에 해당하는지 조건을 따져봐야 한다.1. Optimal Substructure인가하위 문제의 최적의 해를 사용하여 전체 최적의 해를 구할 수 있는지 보자. arr = [5, 3, 7, 8, 6, 2, 9, 4] 라고 하자. 시작은 arr의 가장 왼쪽 값부터 시작한다우선, 5라는 숫자 하나로 만들 수 ..
