[TIL] 2주차_Day3: 자료구조/알고리즘 풀기(3)

 

💡Today I Learned

• 자료구조/알고리즘에 대한 세 번째 이론 및 실습 강의를 진행했습니다.
• 큐, 트리, 힙 자료구조의 개념 및 실습

 

---

 

1. 큐(queue)

- 선입선출(FIFO, First In First Out)

- 큐를 추상적 자료구조로 구현: 1) 배열 2) 연결 리스트(LL)

 

- 배열로 구현한 큐의 연산 복잡도

• size, isEmpty, enqueue, peek: O(1)
• dequeue: O(N) → 맨 앞의 원소를 꺼낸 후, 뒤의 원소들을 앞으로 당겨와야 함

- Doubly LL로 구현한 큐의 연산 복잡도

• size, isEmpty, peek, enqueue, dequeue: O(1) → head와 tail을 이용해 head dummy node의 뒤에 enqueue, tail dummy node의 앞에서 dequeue

- 큐의 활용:

1. 자료를 생성하는 작업, 그 자료를 이용하는 작업이 비동기적(asynchronously)으로 일어나는 경우 → 자료가 생성되는 곳 & 활용되는 곳 연결하기 위해 큐를 이용함
   • ex) producer가 item을 queue에 넣고, consumer는 queue에서 먼저 들어온 item을 사용
2. 자료를 생성하는 or 이용하는 or 두가지 모두 작업이 여러 곳에서 일어나는 경우
3. 자료를 처리해 새로운 자료 생성, 나중에 그 자료를 또 처리해야하는 작업의 경우 (순서를 고려해야 함)

 

2. 환형 큐(Circular Queue)

- 정해진 개수의 저장 공간을 원형으로 구성, 돌려가며 이용

- 배열과 front, rear 포인터(인덱스)를 이용해 구현 가능

 

3. 우선순위 큐(Priority Queue)

- 원소들의 우선순위에 따라 큐에서 빠져나오는 방식의 큐

 

- 우선순위 계산 시기: 1) enqueue 시 우선순위 순서 유지  2) dequeue 시 우선순위 높은 것 선택

• 1)이 더 유리 → dequeue할 때마다 모든 데이터를 탐색해 우선순위를 계산해야 함, 큐의 길이에 비례한 시간 소요

- 구현 방식: 1) 선형 배열 이용  2) LL 이용

• 2)가 더 유리 → enqueue시 우선순위를 따르기 위해 리스트의 중간에 원소를 삽입해야 하는 작업이 빈번, LL이 해당 연산에서 더 유리함 (배열은 하나씩 뒤로 밀기 / LL은 링크를 끊고 새 노드와의 링크 만들기)

- 주의할 것:

enqueue 구현 시 노드가 삽입될 위치를 파악해야 함

→ 이 때 양방향 연결 리스트의 getAt() 메소드 사용하지 x

→ getAt(i)를 호출할 경우 i번째 노드까지 리스트를 순회함

→ 따라서 1~nodeCount 위치의 아이템을 모두 getAt()으로 탐색할 경우 getAt() 메소드 안에서 1+2+..+nodeCount 번의 탐색이 발생하는 것

 

4. 트리 (Tree)

- 2차원 자료구조, 정점(node)와 간선(edge)를 이용

 

- 노드의 종류: 부모 노드, 자식 노드, 조상 노드(부모의 부모.. 노드), 후손 노드(자식의 자식.. 노드)

• 하나의 자식 노드는 하나의 부모 노드만 가질 수 있음
• 하나의 부모 노드는 여러 개의 자식 노드를 가질 수 있음

- 노드의 수준(level): 루트 노드는 level 0, 아래로 내려갈 수록 +1 → 루트 노드로부터 해당 노드로 도달하기까지 거쳐야하는 엣지의 개수로 해석 가능

- 트리의 높이 or 깊이(height or depth): 최대 수준(level) + 1

- 노드의 차수(degree): 자식(부분 트리, sub tree)의 수 = 자식 노드로 연결되는 엣지의 수

 

- 이진 트리 (Binary Tree): 모든 노드의 차수가 2 이하인 트리 (자식 노드를 최대 2개 가질 수 있음)

• 재귀적 성질: 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (왼/오 서브트리 역시 이진 트리)  or 빈 트리 (재귀의 종단 조건)

- 포화 이진 트리 (Full Binary Tree): 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리, 높이가 k이고 노드 개수가 2^k - 1인 이진트리

 

- 완전 이진 트리 (Complete Binary Tree): 높이 k = 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리 + 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

 

5. 이진 트리 (Binary Trees)

- 연산:

1. size: 트리에 포함된 노드의 수
2. depth: 트리의 깊이 (또는 높이), 전체 이진 트리의 depth = max(왼쪽 서브 트리의 depth, 오른쪽 서브 트리의 depth) + 1
3. 순회 (traversal):
   • 깊이 우선 순회(Depth First Traversal) _ 중위(inorder), 전위(preorder), 후위(postorder) *) root노드 기준
   • 너비 우선 순회(Breadth First Traversal)

 

6. 깊이 우선 순회(DFT)

- 중위 순회: left sub - self - right sub

- 전위 순회: self - left sub - right sub

- 후위 순회: left sub - right sub - self

 

7. 넓이 우선 순회(BFT)

- 한 노드 방문 시 나중에 방문할 노드들을 순서대로 기록 → queue 이용

 

 

8. 이진 탐색 트리(Binary Search Tree)

- 원소들이 완전히 크기 순으로 정렬됨

 

9. 힙(Heap)

- 이진 트리의 한 종류 (이진 힙)

- 1) 루트 노드가 언제나 max or min 값을 가짐 (max heap, min heap) → 느슨한 정렬

- 2) 완전 이진 트리임

 

- min/max heap의 응용

1. 우선순위 큐:
   • enqueue할 때 '느슨한 정렬'을 이루고 있도록 함 → O(logN)
   • dequeue할 때 최댓(혹은 최솟)값을 순서대로 출력 → O(logN)
2. 힙 정렬:
   • 정렬되지 않은 원소들을 아무 순서대로 max(min) heap에 삽입 → O(N * logN)
   • 삽입 완료 후 힙이 빌 때까지 하나씩 꺼내기 →  O(N * logN)
   • 따라서, 정렬 알고리즘의 복잡도 → O(N*logN) (logN 연산을 N개 원소에 대해서 모두 수행하므로)

- 주의할 점: 특정 키 값을 가지는 원소를 빠르게 찾는데 적합한 자료구조는 아님 (traverse, search 와는 heap에서 얻고자 하는 연산이 x..)

 

- 배열을 이용한 이진 트리 표현: 노드 번호 m >= 1 (1부터 numbering → 인덱스 계산 시 더 편리)

• 왼쪽 자식 = 2 * m
• 오른쪽 자식 = 2 * m + 1
• 부모 노드 = m // 2

- max heap에 원소 삽입: O(logN) _ 원소의 개수 N개  → 부모 노드와 대소 비교의 최대 횟수 (level 만큼)

- max heap으로부터 원소 삭제: 2 * logN = O(logN) → 자식 노드들과 대소 비교의 최대 횟수 (자식 노드 2개, level만큼 수행)

- maxHeapify() 메소드: max heap에서 최댓값을 출력한 다음, 해당 힙을 다시 max heap으로 구성함 → 재귀로 구현

 

---

📒 Furthermore

• 양방향 연결 리스트로 큐를 구현했을 때 각 연산의 시간 복잡도 생각해보기
• 양방향 연결 리스트로 '우선순위 큐' 구현했을 때 vs max(or min) heap으로 '우선순위 큐' 구현했을 때 시간 복잡도 차이 생각해보기
  • enqueue: Doubly LL → O(N) ?? / max(min) heap → O(logN)
  • dequeue: Doubly LL → O(1) / max(min) heap → O(logN)
• 이진 탐색 트리 ~ 힙까지 강의 듣고 실습 문제 풀이