Minwook’s portfolio

힙(heap)이란? 이진트리의 형태를 띄고 있는 자료구조, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬된다. 우선순위 큐를 구현할때 가장 적합한 자료구조이다. (우선순위 큐에 힙이 포함되는 형태) *Root : 트리에서 최상위 Node 힙의 특징 우선순위가 높은 요소가 먼저 나온다. Root가 최대값이 되는 최대 힙(오름차순)과 가장 작은 값(내림차순)이 되는 최소 힙 두가지 있다. 자바스크립트에서는 직접 구현해야 하는 단점. 완전 이진 트리의 높이는 logN이기 때문에, 노드 추가 삭제시 시간복잡도는 O(logN) 지수시간을 가진다. *빠름 O(1) < O(logN) < O(N) < O(NlogN) 느림 힙에서 추가를 구현할때 알고리즘 (최대힙) 1. 새로운 요소를 추가..

Hashtable이란? key와 value를 받아 hashing하여 나온 index에 값을 저장하는 선형자료구조, 삽입시 시간복잡도는 O(1), key를 알고 있다면 탐색과 삭제도 O(1)로 빠른속도로 수행가능. 해쉬충돌이란? 서로 다른 input Data 가 같은 hash 함수를 통해 hashing후 결과값이 같을때 해쉬충돌이 일어날 경우, 같은 버킷에 저장되게 되므로 원하지 않는 결과를 불러올 수 있다. 해쉬충돌을 해결하는 4가지 방법 1.선형탐사법 충돌이 발생하면 기존 버킷에서 옆으로 한칸 이동하여 Data를 저장한다. 단순하지만 충돌이 여러번 일어날 결우 특정영역에 데이터가 모일 수 있는 단점이 있다. 또한 충돌이 발생하지 않을 때까지 이동해야 하므로 최악의 경우에는 탐색에 선형시간 O(n)이 소..