인프런 커뮤니티 질문&답변

Raerae님의 프로필 이미지
Raerae

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6주차 개념 #1. 이분탐색(Binary Search)

LIS 질문

해결된 질문

작성

·

124

0

안녕하세요 선생님! 간단한 질문인데요,

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

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

미리 감사드립니다!

답변 1

1

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 ㅎㅎ

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

>> 네 맞습니다.

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

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



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

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

감사합니다.

강사 큰돌 올림.


Raerae님의 프로필 이미지
Raerae

작성한 질문수

질문하기