LIS 질문

안녕하세요 ㅎㅎ

LIS 요소의 크기를 구하는 건 dp와 lower_bound() (또는 binary search), 이렇게 두가지 방법을 이용할 수 있는 것으로 이해했는데요.

>> 네 맞습니다.

그럼 어떤 요소들이 있는지 trace하는 방법은 dp로밖에 구현을 못하는 걸까요? 즉, 무조건 O(N^2)이라는 시간복잡도를 가지는 건가요?

>> 네 맞습니다. 정확하게는 O(N^2)이라는 시간복잡도를 가지며 trace를 위한 배열 하나를 기반으로 구축해야 합니다.lower_bound()의 경우 원본 배열을 훼손한 새로운 배열을 만들며 만드는 것이라... 해당 방법으로는 불가능합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.