orderstatictree1 [PS를 위한 자료구조 6강] 세그먼트 트리의 응용 (Orderstatic Tree) PS를 위한 자료구조 1-6강 # 다양한 세그먼트 트리 테크닉 (Orderstatic Tree) # 에 대해 알아보겠습니다. Orderstatic tree는 한국말로 딱히 번역이 되어있는 것은 없는 것으로 알고 있습니다. 아래의 문제를 볼까요? [가운데를 말해요] https://www.acmicpc.net/problem/1655 이 문제를 어떻게 해결할 수 있을까요? 다음과 같은 자료구조를 생각해봅시다. (1) 정렬 순서을 유지한채로 삽입하는 것이 O(n)보다 작은 시간복잡도로 가능 (2) 정렬된 자료구조의 특정 인덱스 접근울 O(n)보다 작은 시간복잡도로 가능 언뜻보면 별거 아닐 것 같지만, 절대 평범한 리스트로는 수행할 수 없습니다. 이분탐색으로 삽입할 위치를 O(logN)에.. 2022. 3. 24. 이전 1 다음