[2024 동계 모각코] 6주차 계획

6주차 계획

개요

6주차(2. 6 ~ 2. 11)의 계획입니다.

• 21장 트리의 구현과 순회
  • 문제: TRAVERSAL
  • 문제: FORTRESS
• 22장 이진 검색 트리
  • 문제: NERD2
  • 문제: INSERTION
• 23장 우선순위 큐와 힙
  • 문제: RUNNINGMEDIAN

---

21장 트리의 구현과 순회

문제: TRAVERSAL

이진 트리의 전위 순회의 출력문과 중위 순회의 출력문을 가지고 후위 순회의 출력문을 만드는 문제입니다.

전위 순회를 기반으로 중위 순회의 $index$를 탐색해 왼쪽 & 오른쪽 노드 구별을 하는 알고리즘을 설계하여 풀었습니다.

문제

코드

비슷한 백준 문제는 백준 4256 트리, 백준 2263 트리의 순회 문제가 있습니다

문제: FORTRESS

트리의 지름 문제(Tree Diameter Problem)를 풀어봅시다.

문제

코드

포스트

---

22장 이진 검색 트리

문제: NERD2

비 지배 순서쌍의 개수를 각 순서쌍이 추가될 때마다 구하는 문제를 풀어봅시다.

문제

코드

포스트

문제: INSERTION

정렬 과정의 “역추적(Reverse Engineering)” 문제를 트리 구조를 통해 $O(n \log n)$시간 안에 풀어봅시다.

이것을 세그먼트 트리로 풀 수도 있지만, 트립(Treap)을 이용해서 구현해봅시다.

문제

코드

포스트

---

23장 우선순위 큐와 힙

문제: RUNNINGMEDIAN