최근 LeetCode 등의 알고리즘, 구현 문제들을 풀면서 자료 구조를 직접 구현해보기 시작했다. Heap에 대한 개념은 어느정도 있었다고 생각했는데, 막상 구현하려고 보니 입력, 삭제 시 어떻게 정렬을 보장할 수 있지? 에서 멈칫했다. 생각을 정리하고 코드를 짜보려 했지만, 선뜻 키보드에 손이 가지 않아 정리하는 마음으로 이 포스팅을 작성하게 되었다. 힙(Heap)힙은 트리 기반의 자료구조이며, 반드시 부모노드와 자식 노드 사이에는 대소 관계가 성립해야한다는 규칙이 있다. 힙에는 규칙에 따라 최소 힙(Min Heap), 최대 힙(Max Heap)이 있으며, 위 대소관계에 따라 부모 노드가 자식 노드보다 작다면 최소 힙, 반대의 경우는 최대 힙이라 부른다. 이 대소 관계는 반드시 부모 노드와 자식..

해시테이블 (hashtable) Key, Value 로 데이터를 저장하는 자료구조 중 하나이며 데이터를 빠르게 검색할 수 있는 자료구조이다. 빠른 검색을 할 수 있는 이유는 내부적으로 버킷(배열)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. (Key, Value)가 ("Becca", "+1 424 999 0000")인 데이터를 해시 테이블에 저장한다고 할 때, index = hash_function("Becca") % Index을 통해 Index값을 계산한 뒤, array[Index] = "+1 424 99..

트리구조란? 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프이다. 회사의 조직도 내 컴퓨터\C:\Program Files\..... 트리 용어 용어 설명 루트(root) 노드 맨 위에 위치한 노드이며, 부모노드 라고 함 리프(leaf) 노드 자식이 없는 최하단 노드, 단말(terminal) 노드 라고도 함 내부(internal) 노드 리프노드가 아닌 노드, 가지(branch) 노드 라고도 함 간선/엣지/링크/브랜치 노드들끼리의 연결선 노드의 차수 한 노드가 가진 서브트리의 차수 트리의 차수 트리노드들의 차수 중 최대차수 서브트리(sub-tree) 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리 레벨(level) 0이나 1부터 시작하며 높이를 정의함 높..