데이터 엔지니어링 데브코스 2주차 - 수요일

학습주제
[수업] 자료구조/알고리즘
큐 : 큐, 환형 큐, 우선순위 큐
트리 : 이진트리, 이진탐색트리, 힙

 

주요내용

1. 큐(Queue)

• 스택과 동일하게 자료를 보관할 수 있는 선형구조의 자료구조
• 선입선출 구조(FIFO) - 먼저 들어간 데이터가 먼저 나온다.

2. 큐의 활용

• 자료를 생성하는작업과 이용하는 작업이 비동기적으로 일어나는 시스템에서 주로 활용한다.
• 예) 실시간 분산처리 플랫폼인 Kafka의 producer와 consumer

https://www.cloudkarafka.com/img/blog/kafka-broker-beginner.png

3. 환형 큐(Circular Queue)

• 실제 시스템이나 프로그램에서는 정해진 개수와 저장 공간을 돌려가며 이용한다.
• 큐가 가득차면 더이상 데이터를 넣을 수 없기 때문에큐 길이를 정확히 알고 있어야 한다.
• 배열로 만들경우 front와 rear의 포인트와 나머지 연산(%)을 적절히 활용하여 환형 구조를 활용한다.

4. 우선순위 큐(Priority Queues)

• 큐의 FIFO 원칙을 따르지 않고, 원소들의 우선순위에 따라 큐에서 데이터를 가져오는 방식
• 효율적인 우선순위 큐 구현 방식은 Enqueue(삽입)할때 우선순위 순서를 유지하는 방식이다.
• 우선순위에 따라 데이터 삽입이 빈번하기 때문에 연결리스트로 구현하는 것이 효율적이다.

5. 트리(Tree)

• 정점(node)과 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조
• 노드의 수준(level)은 제일 상위 노드는 레벨 1(혹은 0)부터 시작하고, 뿌리 노드부터 자기 자신까지 도달하기 위한 간선의 개수와 동일
• 트리의 높이 : 노드의 최대 수준 +1로, 깊이라고도 한다.
• 노드의 차수 : 자식(서브트리)의 수, 자식 노드에 이어지는 간선의 개수이며, 자식이 없는 노드는 leaf node라고 한다.

6. 이진트리(Binary Tree)

• 트리에 포함되는 노드의 차수가 2이하인 트리를 말한다. 
• 포화이진트리 : 모든 레벨에서 노드들이 모두 채워져 있는 이진트리
• 완전이진트리 : 높이 k - 1까지 모든 레벨에서 노드들이 모두 채워져 있고, 높이 k에는 왼쪽 부터 노드들이 채우져 있는 트리

7. 깊이 우선 순회

• 깊이를 기준으로 하되 노드 순회 방향에 따라 3가지 종류가 있다.
• 중위(inorder) 순회 : Left subtree → 자기 자신 → Right subtree
• 전위(preorder) 순회 : 자기 자신 → Left subtree -> Right subtree
• 후위(postorder) 순회 : Left subtree → Right subtree → 자기 자신
• 재귀적 방법으로 순회를 쉽게 할 수 있다.

8. 넓이 우선 순회

• 수준이 낮은 노드를 우선으로 방문하고, 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서를 따르고, 왼쪽 자식 노드를 먼저 방문한다.
• 큐를 활용하여 나중에 방문할 노드를 기록하는 방식으로 순회한다.

9. 이진 탐색 트리

• 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모든 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 이때 중복된 데이터는 없다.
• 트리의 왼쪽과 오른쪽 구조의 불균형이 있을 때 효율적이지 못할 수 있다. 그래서 AVL 트리나 레드블랙 트리는 높이의 균형을 유지함으로써 시간복잡도를 O(logn)의 탐색을 보장하여 이진탐색 트리의 단점을 보완한다.

10. 힙(Heaps)

• 이진 트리의 한 종류로, 이진 힙이라고도 불린다.
• 성질 : 루트 노드가 언제나 최댓값 혹은 최솟값을 가진다(최대 힙, 최소 힙), 완전 이진트리여야 하며, 이진 탐색트리와 달리 왼쪽과 오른쪽 노드가 상하 관계가 없는 다소 느슨한 형태를 가지고 있다.

느낀점

기존에 알고있던 자료구조들도 실제 구현을 하다보니 좀 더 어렵게 다가오는 부분이 있었다. 각 자료구조별로 가지는 효율성과 실제 산업에서 활용하는 부분에 대해서 명확히 이해하는데 중점을 두고 공부해야겠다.