큐, 트리, 힙

데이터 엔지니어링 데브코스 Day 3

- 자료구조 및 알고리즘 풀기 3

 

 

🚀 큐 (Queue)

큐

• 자료를 보관할 수 있는 선형 구조
• 자료를 넣을 때에는 한 쪽 끝에서 넣고, 꺼낼 때는 반대쪽에서 꺼냄
  • 넣는 것은 인큐(enqueue) 연산
  • 빼는 것은 디큐(dequeue) 연산
• 선입선출 (FIFO, First-In-First-Out) 특징을 가지는 선형 자료구조
• e.g. 프린트에 인쇄할 문서 보낼 때, 대기열 등

 

🚀 환형 큐 (Circular Queue)

환형 큐, 원형 큐

• 원형 큐라고도 불림
• 큐의 한 종류로 원형 구조를 갖추어 FIFO 방식을 사용
• 정해진 개수의 저장 공간을 돌려가며 사용
• 원형으로 데이터를 저장하며 앞과 뒤가 연결되어 순환
• Front는 큐의 맨 앞 요소를 가리키고, Rear는 큐의 맨 뒤 요소를 가리킴
  • 데이터 추가하면 Rear 이동
  • 데이터 제거하면 Front 이동

 

🚀 우선순위 큐 (Priority Queue)

우선순위 큐

• 저장되는 데이터는 우선순위를 가지며, 가장 높은 우선순위를 가진 데이터가 항상 먼저 꺼내지게 됨
• 일반 큐와는 달리 들어간 순서가 아닌, 데이터의 우선순위에 따라 처리됨
• Enqueue 할 때 우선순위 순서를 유지하는 방법과 Dequeue 할 때 우선순위 높은 것을 선택하는 방법이 있지만 전자가 효율적
• e.g. CPU 작업 스케줄링, 네트워크 라우팅 등

 

🚀 트리 (Tree)

트리의 종류

트리

• 계층적인 구조를 갖는 비선형 자료구조
• 노드들이 간선으로 연결되어 있음
• 하나의 루트 노드에서 시작하여 여러 개의 자식 노드를 갖는 부모-자식 관계로 구성
• 각 노드는 자식 노드를 가질 수 있고, 각각의 자식 노드는 또 다시 자식 노드들을 가질 수 있음

 

🚀 이진 트리 (Binary Tree)

이진트리

• 트리의 종류 중 하나로 모든 노드의 차수가 2 이하인 트리

 

🚀 포화 이진 트리 (Full Binary Tree)

포화 이진 트리

• 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
• 모든 내부 노드가 두 개의 자식을 가진 이진 트리
• 내부 노드가 0개 또는 2개의 자식을 가짐

 

🚀 완전 이진 트리 (Complete Binary Tree)

완전 이진 트리

• 모든 레벨에서 노드가 왼쪽에서 오른쪽으로 채워진 이진 트리
• 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차있고, 마지막 레벨에서는 왼쪽부터 순서대로 노드가 채워짐

 

🚀 넓이 우선 순회 (Breadth First Traversal)

넓이 우선 순회

• 수준(level)이 낮은 노드를 우선 방문
• 루트 노드에서 시작하여 각 레벨의 노드를 왼쪽에서 오른쪽으로 방문

 

🚀 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리

• 각 노드의 왼쪽 하위 트리에는 해당 노드 값보다 작은 값들만, 오른쪽 하위 트리에는 해당 노드 값보다 큰 값들만 위치하는 이진 트리
• 데이터를 빠르게 검색할 수 있다는 장점
• 트리가 균형을 이루지 않으면 검색 성능이 저하될 수 있음
  • 이를 해결하기 위해 AVL 트리, 레드-블랙 트리 등의 균형 이진 탐색 트리가 이용됨

 

🚀 힙 (Heap)

최소힙, 최대힙

• 이진 트리의 한 종류 (이진 힙 - binary heap)
• 부모 노드의 값이 항상 자식 노드의 값보다 크거나(최대힙), 작거나(최소힙) 같은 규칙을 만족하는 이진 트리
  • 루트 노드는 항상 최댓값 또는 최솟값을 가짐
• 완전 이진 트리여야 함