구간 보최소 문제 = The Range Co - minima Problem

국문 초록 (Abstract)

각 원소 a₁가 1과 n사이의 정수인 배열 A =(a₁, a₂,..., a_n)가 있을 때, A를 전처리하여, 주어진 질의 인덱스 쌍 i, J (i < J)에 대하여 {a₁, ai +₁, ..., a_j}에 들어 있지 않은 가장 작은 양의 정수를 빨리 구하는 문제를 본 논문에서 고려한다. 즉, A를 전처리하여 어떤 자료를 구축한 후, 온라인으로 주어지는 i, J에 대해서 min ({1,2,..., n+1} - {a₁, ai+₁, ..., a_j})를 신속하게 구하는 것이다. 본 논문에서는 두 개의 해를 제시하는데, 첫번째 해는 O(n²) 전처리 시간과 O(1) 질의응답 시간을 갖으며, 두번째 해는 O(n log n) 전처리 시간과 O(n log n) 질의응답 시간을 갖는다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. O(n²) 전처리 시간과 O(1) 질의응답 시간을 갖는 해
• 3. O(n log n) 전처리 시간과 O(log n) 질의응답 시간을 갖는 해
• 참고문헌