10일차 강의 (22, 23강)

이진검색트리 (22강)

insert, erase, find, update → O(log N)

내부적으로 원소가 크기 순으로 정렬되어 있음 (★장점)

 

자가 균형 트리를 사용해야 O(log N)이 보장 됨 (편향된 트리 때문)

 

STL - set, multiset, map

set에서는 원소가 정렬되어있기 때문에 unordered_set과 달리 대소비교해서 값 찾는 연산이 O(log N)에 가능

iterator를 활용하여 prev, next, advance, lower_bound, upper_bound, find등의 연산이 O(log N)에 제공

 

O(log N)이지만 다른 O(log N) 연산에 비해 느린편임.

 

우선순위 큐 (23강)

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

 

1. 원소의 추가가 O(lg N)

2. 우선순위가 가장 높은 원소의 확인이 O(1)

3. 우선순위가 가장 높은 원소의 제거가 O(lg N)

 

STL

priority_queue (기본 선언시 최대 힙임)

→ 최소힙이 필요할 경우 priority_queue<int, vector<int>, greater<int>>로 선언해야 함

 

priority_queue에서 할 수 있는건 set에서도 할 수 있고 시간복잡도도 동일하지만, 

priority_queue는 set보다 수행 속도가 빠르고, 공간도 적게 차지한다.

 

priority_queue에서 비교 함수를 사용할 때에는 클래스를 만들어서 사용해야 함

class cmp {

public:

  bool operator() (int a, int b) {

         // 내용 

  }

};