맵, 집합, 우선순위 큐

맵 c++(Map) python(Dictionary)

map 형식은 키와 밸류 쌍으로 이루어져있으며 대표적으로 JSON의 형식이다 (key : value)

key는 중복될 수 없는 고유한 값이여야하지만 value는 중복이 가능하다

c++에서는 logN의 시간 복잡도를 가지고(정확히는 밑을 2로 가지는 log2 N ) python에서는 1의 시간 복잡도를 가진다(파이썬에서 유리하다)

 

집합 set

집합은 중복이 되지 않고(중복된 값을 넣을 수는 있지만 1개만 남는다) set 함수로 사용할 수 있다

c++에서는 logN의 복잡도 python 에서는 1의 복잡도를 가진다

python에서 s.pop()으로 제거시 무작위로 1개의 값이 제거된다, s.remove('원하는값')으로 원하는 값을 제거할 수 있다

집합과 맵은 유사한 점이 많다, 따라서 집합으로 풀 수 있는 문제는 맵으로도 풀 수 있고 역방향 역시 가능하다

 

우선순위 큐 Priority Queue (Heap)

내부적으로 이진트리의 힙구조로 이루어져 있다

최상단 노드를 root node 라고 한다, 루트노드가 최댓값일 경우 max-heap 최솟값일 경우 min-heap 이라고 한다

c++에서는 max-heap을 python 에서는 min-heap을 기본사항으로 제공한다

pop() 메소드를 사용할 경우 max-heap: 가장 큰 값, min-heap: 가장 작은 값이 제거된다