알고리즘 문제풀이
우선순위 큐 (Heap) 구현하기
Heap알고리즘으로 백준 1655번 가운데를 말해요를 풀어야하기도 하고, 검색 시스템을 구현할 때 Heap알고리즘을 사용할 예정이었기 때문에 한 번 정리하고자 했다. #1 우선순위 큐와 Heap의 정의 힙은 자료구조의 형태를 의미한다. 우선순위 큐란 데이터를 큐처럼 추가/삭제할 수 있는 자료구조이면서 동시에, 데이터를 출력할 때 넣은 가중치를 기준으로 높은 우선순위부터 뽑히는 것을 의미한다. 우선순위 큐를 구현할 때, 힙 자료구조를 사용하기 때문에 둘을 함께 취급하는 경우가 있다. 이름은 queue이지만, 정확히 queue를 사용하는 건 아니고, 트리 형태를 사용한다. #2 힙 자료구조의 특징 최대 힙 - 부모 노드는 자식 노드보다 크거나 같은 값을 가짐. 최소 힙 - 부모 노드가 자식 노드보다 작거나 ..
2024. 1. 8. 16:20
