시간 복잡도1 [Algorithm] 최장 증가 부분 수열(LIS) DP 문제인 LIS 문제를 풀기 위해 LIS 알고리즘을 공부했습니다. 제가 공부한 내용을 바탕으로 작성했습니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 최장 증가 부분 수열(LIS)이란? 수열이 주어지고 해당 수열에서 몇개의 수를 제거했을 때 부분 수열을 만들 수 있습니다. 부분 수열 중에서 오름 차순으로 정렬되고, 길이가 가장 긴 부분 수열을 최장 증가 부분 수열(LIS)이라고 합니다. 그렇다면 이해를 위해 예를 들어보도록 하겠습니다. {3, 5, 7, 9, 2, 1, 4, 8} 수열이 있습니다. 몇개의 수를 제거하여 부분 수열을 만들면 {3, 5, 7, 9, 2} {5, 7, 9} {3, 5, 7, 8} {3, 5, 7, 9} 등을 만들 수 있습니다. ✔ {3, 5,.. Algorithm 2022. 8. 17. 이전 1 다음