괴발자의 전공노트

#큐(Queue) 란? 큐(Queue)는 대표적인 자료구조 중 하나로 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 형태를 가진 자료구조를 의미한다. 쉽게 생각하면 대기열을 생각하면 된다. 예를 들어 손님이 많은 가게에서 웨이팅을 할 때 가장 먼저 기다린 사람이 가게에 자리가 생기면 가장 먼저 입장하는 것과 같다. 이렇게 큐(Queue) 와 같은 형태를 FIFO(First In First Out) 구조라고 칭하기도 하며 가끔 LILO 구조 라고(Last In Last Out) 칭하기도 한다. 위 그림을 보면 알 수 있듯이 큐(Queue)에 데이터를 넣는 것을 Enqueue라고하며, 데이터를 꺼내는 행위는 Dequeue라고 칭한다. #큐(Queue) 의 종류 1) 큐(Queue) 가장 표준적인 큐(Qu..

힙(Heap) 이란? Heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리의 한 종류이다. Tip! 완전 이진 트리(CBT, Complete Binary Tree) 완전 이진 트리는 노드를 삽입할 때 왼쪽 최하단 노드부터 순서대로 데이터를 삽하는 이진 트리를 의미한다. 힙(Heap)의 구조와 조건 힙은 최대값을 구하기 위한 구조를 가진 최대 힙(Max Heap) 과, 최소값을 구하기 위한 구조를 가진 최소 힙(Min Heap)으로 분류할 수 있다. 힙은 아래와 같이 두 가지 조건을 가지고 있는 자료구조를 의미한다. 최대 힙(Max Heap)의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같아야 한다. 최소 힙(Min Heap)은 반대로 각 노드의 값은 해..