내 잡다한 노트

# 정의 해시테이블은 해시함수를 이용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스삼아 데이터를 key와 함께 저장하는 자료구조이다. # 해시함수 해시 함수의 정의는 key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 해싱이라고 한다. key ---(해시함수)---> 해시 해시는 저장위치 즉 인덱스가 된다. # 해시테이블 구성 key : 해쉬 함수의 input이고, key를 그대로 인덱스로 사용할 경우에는 key의 길이만큼의 정보를 저장해야하는 공간도 따로 마련해야 해서 고정된 길이의 해시로 변경하는 것이다. 해시 함수 : key를 고정된 길이의 해시로 변경해주는 역할을 한다. 서로 다른 key가 해싱후 같은 해시 값이 나오는 경우가 있다. 이를 해시충돌이라고 한다. 이 충돌이 안나올..

우선순위 큐를 위해 만들어진 자료구조이다. 먼저, 우선순위 큐에 대해 짧게 알아보면... # 우선순위 큐 우선순위의 개념을 큐에 도입한 자료구조이다. 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. # 우선순위 큐 이용사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이 중에서 힙으로 구현이 가능하는게 가장 효율적이라고 한다. 힙으로 구현할 시 삽입과 삭제의 시간복잡도는 각각 O(logn)이 된다고 한다. # 힙 heap 완전 이진 트리(Complete tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 완전이진트리는 왼쪽부터 아래쪽으로 삽입해 나간다. 또한 리프노..

# 트리 구조 트리란 Node와 Branch를 이용해, 사이클을 이루지 않도록 구성한 데이터구조. 재귀적인 구조이다. 여러 트리의 구조 중 이진트리 형태의 구조는 탐색 알고리즘 구현을 위해 많이 사용된다. # 용어 Node : 트리에서 데이터를 저장하는 기본 요소 Edge : 각 노드들을 연결하는 선 Root Node : 트리 맨 위에 있는 Node Level : 최상위 노드를 Level 0으로 할 때, 노드의 깊이 Parent Node : 부모 노드. 즉, 자신의 노드 위에 있는 노드 Child Node : 자식 노드. 즉, 자신의 노드 밑에 있는 노드 Leaf Node : 자식 노드가 하나도 없는 노드 Siblings : 동일한 Parent Node를 가진 노드 Depth : 트리에서 최대 Level..