LIS문제 -DP
LIS문제: 최장 증가 부분 수열 배열의 일부분을 순서대로 추출했을 때 크기가 커지는 배열들의 집합 중에서 가장 길이가 긴 수열 찾기 문제의 답은 여러개가 될 수 있다. [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 배열이 있다면 [2, 4, 9] 배열은 정답 후보에 있을 수 있다. 생각해보면 커지는 것을 발견하면 선택하는 식으로 해결한다면? [1,2,9, ~~~] 에서 9를 선택했는데 ~~~부분이 3,4,5,6,7 이렇게 더 긴 조합을 생성할 수 있으므로 유의해야 한다. DP [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 8이 배열의 마지막인 배열들 중 가장 길이가 긴 것은 [8] 하나밖에 없다. [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 2가 배열의 마지막인 부분배열들 ..
2022. 10. 6.
