[알고리즘] LIS 최장 증가 부분 수열, SegmentTree
최장 증가 부분 수열이란? A라는 수열ㄹ에서 연속되는 것과 상관없이 Ai < Aj (단, i < j)를 만족하는 부분 수열입니다. [10, 20, 10, 30, 20, 50] 위와 같이 수열이 주어졌을 때, [10, 20] [10, 20, 30] [10, 20, 30, 50] ... 모두 증가 부분 수열이며, 그 중 가장 길이가 긴 부분 수열이 최장 증가 부분 수열입니다. 어떻게 구하나? 동적계획법을 이용하여 구할 수 있습니다. 수열 A가 주어졌을 때, D(i)를 i번째 수를 부분 수열의 마지막으로하는 부분 수열 중 가장 길이가 긴 수열의 길이라고 한다면, D(i)는 Ai보다 앞에 있고 Ai보다 작은 Aj의 j에 대하여 D(j)가 가장 큰 값 + 1이될 것입니다. 즉 index 0부터 차례로 순회하며 D..
2022. 10. 10.
