힙 (Heap)
- 이진 트리를 이용한 자료구조
- 우선순위 큐
일반적인 FIFO(First In First Out)의 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐
우선순위 큐는 자료구조가 아니라 개념일 뿐으로, 다양하게 사용 가능하다. - 힙
이진트리 형태로, 우선순위가 높은 요소가 먼저 나가기 위해 요소 삽입 / 삭제 시 바로 정렬됨
우선순위가 높은 요소가 먼저 나간다.
Root 가 가장 큰 값이 되는 최대 힙 (Max Heap), 가장 작은 값이 되는 최소 힙 (Min Heap)
자바스크립트에서는 힙을 직접 구현해서 사용해야 한다.
비슷하지만, 힙 != 우선순위 큐 - 힙 요소 추가 알고리즘
요소 추가 (이진트리 가장 마지막 노드에 추가)
-> 추가된 요소가 부모 노드보다 우선순위가 높다면 부모 노드와 순서를 바꿈
-> 반복 ... 결국 가장 우선순위가 높은 노드가 Root 가 된다.
O(log N) 의 시간복잡도를 가짐 - 힙 요소 제거 알고리즘
요소 제거는 Root 노드만 가능하다.
Root 노드가 제거
-> 가장 마지막 노드가 Root 에 위치 -> Root 노드의 두 자식 노드 중 더 우선순위가 높은 정점과 바꾼다.
-> 두 자식 노드가 우선순위가 더 낮아질 때 까지 반복
O(log N) 의 시간복잡도를 가짐
트라이
- 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
- 특징
자동완성, 사전 찾기 등에 응용
문자열 탐색 시, 단순 비교보다 효율적으로 찾을 수 있다.
탐색 / 삽입은 O(문자열 길이) 만큼 걸린다.
각 노드가 자식에 대한 링크를 전부 가지고 있어, 저장 공간을 더 많이 사용한다. - 구조
Root 는 비어있다.
각 간선(링크) 는 추가될 문자를 key 로 가진다.
각 노드는 이전 노드의 값 + 간선의 key 를 값으로 가진다.
해시 테이블과 연결리스트로 구현 가능
쉽지 않습니다 ㅜㅜ
점점 더 이해하는데 많은 시간이 필요하게 되어 오늘은 강의를 조금밖에 못들었습니다..
(실습 문제풀이 하느라 시간이 다 가버렸네요..)
프로그래머스 연습문제에서 힙의 개념을 사용하는 문제를 봤던 것 같은데.. 그 당시에는 힙의 개념을 몰라서 못풀고 넘어갔습니다.
힙부분 복습 후, 기억을 더듬어서 무슨 문제 였는지 확인하고 재도전 해보려고 합니다!
자동완성 기능이 정말 거창하고 복잡한 프로그래밍으로 만들어지는 줄 알았는데, 하나의 자료구조로 구현이 가능했다는 사실을 처음 알게 되었습니다!
그런데 아직 어떻게 응용해서 써야할지는 조금 감이 안잡힙니다 ㅜㅜ 과제 제출 해야하는데.. 얼른 익혀보도록 하겠습니다.
주말에 밀린부분을 최대한 해결하면서 공부해 보도록 하겠습니다! 🙃
프론트엔드