PS 풀이 및 정리/테크닉 정리 (1) 썸네일형 리스트형 자료구조 덱(Deque)의 활용 (feat. Priority Queue) 덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 \(A_1, A_2,..., A_N\)이 주어질 때 임의의 상수 B에 대해 \(A_{i-B}\) ~ \(A_i\) 의 최대, 최소 같이 데이터를 가진 정보들을 특정한 기준에 따라 나열할 때 가장 우선순위가 높은 값을 모든 i에 대해 시간 복잡도 O(N)으로 찾아줄 수 있다. 위와 같은 상황에서 A라는 배열의 각 원소에 \(V_i\)라는 우선순위가 주어져 있다고 하자. 우리는 덱에 다음과 같은 성질을 만족시키도록 자료들을 넣고 뺄 것이다. 성질 : \(I_i\)를 덱의 앞에서부터 i번째에 있는 원소가 가지는 배열 A에서의 인덱스라고 했을 때, i>n>>l; .. 이전 1 다음