다나리

힙 우선순위 큐를 구현하는 가장 효율적인 자료구조이다. 완전 이진 트리의 일종이며, 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태 (느슨한 정렬 상태)를 유지한다. 힙 트리에서는 이진 탐색 트리와 달리 중복된 값을 허용한다. 배열을 이용하여 구현한다. 0번 인덱스는 사용되지 않으며, 특정 위치의 노드번호는 변하지 않는다. 힙의 종류 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 힙의 삽입 마지막 노드 다음 노드에 새로운 요소를 삽입한다. 삽입한 노드가 부모 노드보다 크면 자리를 바꾼다. 부모 노드가 삽입한 노드보다 클 때까지 반복한다. 힙..

트리란? 하나의 루트 노드를 가지며, 0개 이상의 자식 노드를 갖고 있다. 각 노드들은 간선으로 연결되어 있다. 비선형 자료구조이며 계층적 관계를 표현한다. 사이클이 없는 하나의 연결그래프이다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 루트에서 어떤 노드, 또는 임의의 두 노드 간의 경로는 유일하다. 순회하는 방법에는 Pre-Order, In-Order, Post-Order가 있다. 관련 용어 노드의 크기(Size): 자신을 포함한 모든 자손 노드의 개수 노드의 깊이: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 간선의 수 노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합 노드의 차수(Degree): 노드의 자식 수 트리의 차수: 트리의 최대 차수 트리의 높이: 루트 노드에서 가장 깊숙..

스택 (Stack) 스택은 후입선출(LIFO, Last-In-First-Out) 구조로, 데이터를 쌓아올린 형태의 자료구조이다. 한 곳에서만 데이터가 출입할 수 있다. top은 가장 최근에 들어온 자료를 가리키고 있으며, push를 통해 자료를 삽입하고, pop을 통해 자료를 삭제한다. 큐 (Queue) 큐는 선입선출(FIFO, First-In-First-Out) 구조로, 한 쪽에서 자료를 삽입하고, 다른 한 쪽에서 자료가 삭제되는 형태의 자료구조이다. 삭제 연산을 수행하는 곳은 front이며, 삽입 연산을 수행하는 곳은 rear이다. enqueue를 통해 자료를 삽입하고 dequeue를 통해 자료를 꺼낸다.