코딩테스트 자료구조 (2)

📖 우선순위 큐 (Priority Queue)

• 데이터를 우선순위에 따라서 처리하고 싶을 때 사용
• 힙(heap)을 이용하여 구현
• 삽입, 삭제 O(logN)
• 탐색 O(N)

힙 (Heap)이란?

---

먼저 힙에 대해서 알아야한다.

힙이란 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

• 최대 힙 (Max Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
  • 루트 노드 : 키 값이 가장 큰 노드
• 최소 힙 (Min Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
  • 루트 노드 : 키 값이 가장 작은 노드

c++에서 우선순위 큐 사용법

---

C++ : max-heap

//C++
#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq;
pq.push(7);
pq.push(5);
pq.push(4);
printf("size: %d\n", pq.size());
while(!pq.empty()){
  printf("%d\n", pq.top());   //맨 위의 값 출력
  pq.pop();                   //맨 위의 값 삭제(출력은 안함)
}

python에서 우선순위 큐 사용법

---

Python : min-heap

#Python
"""
#thread-safe 라서 밑에 코드가 더 빠름
from queue import PriorityQueue
q = PriorityQueue()
q.put(7)
q.put(5)
q.put(4)
print("size: ", q.qsize())
while not q.empty():
print(q.get())              #pop
"""
import heapq
heap = []
heapq.heappush(heap, 7)
heapq.heappush(heap, 5)
heapq.heappush(heap, 4)
print("size: ", len(heap))
while len(heap) > 0:
  print(heapq.heappop(heap))

📖 맵 Map (Dictionary)

• key-value 쌍으로 데이터를 저장
  • key끼리는 중복되지 않음(고유값)
• 삽입, 삭제, 탐색 O(logN)
• key는 중복될 수 없음
• key를 이용해서 value를 얻음
• key-value 쌍을 Entry라고 함

언어별 Map 내부 구현

Map 내부 구조	언어	CRUD 시간
red-black tree	C++, Java(treeMap)	O(logN)
hash	Python, Swift, Javascript, Java(HashMap)	O(1)

관련 설명 링크
red-black tree 블로그_설명 위키피디아 시간은 O(logN)이 걸린다.
hash 블로그_설명 시간은 O(1)이 걸린다.

c++에서 map 사용법

---

//C++
#include <iostream>
#include <map>
using namespace std;

map<string, int> m;
m["Jiho"] = 1;
m["love"] = 2;
m["bird"] = 3;
printf("size: %d\n", m.size());
for (auto p : m)
  printf("%s, %d\n", p.first.c_str(), p.second);

python에서 map 사용법

---

#Python
m = {}
m["Jiho"] = 1
m["love"] = 2
m["bird"] = 3
print("size: ", len(m))
for key in m:
  print(key, m[key])

📖 집합 Set

• 중복되지 않는 데이터를 저장
• 삽입, 삭제, 탐색 O(logN)

remove() : 삭제