Jun's

Sort 01. Counting Sort, Radix Sort, Lower Bounds for Sorting (계수 정렬, 기수 정렬, 정렬 알고리즘의 Lower bound)

MIT introduction to Algorithm (6.006) Lecture 7을 기반으로 정리한 내용입니다.

데이터를 비교 및 정렬하는 알고리즘을 위한 ADT를 살펴보고, 각 알고리즘의 Lower Bound를 살펴보자. 그리고 적은 양의 정수로 이루어진 데이터에 대하여, $O(n)$ 의 시간복잡도를 지니는 계수 정렬과 기수 정렬에 대해 살펴보자.

Tree 03-2. Red-Black Tree (레드블랙 트리의 삭제)

이전 게시글에 이어서, Red-Black Tree의 삭제 부분을 알아보는 게시글 입니다. Introduction to Algorithms 책을 참고하였습니다.

정리 하면서도 확실히 이해했다는 생각이 안들어 틀린 부분이 있을 수 있습니다 ㅠㅠ

Tree 03-1. Red-Black Tree(레드블랙 트리)

Red-Black tree는 MIT OCW 강의에서 다루지 않았지만 AVL트리를 공부하다 보니 사실상 AVL트리는 쓰이지 않고 Red-Black Tree나 B-tree, Treaps 같은 구조를 쓴다는 이야기를 듣고 호기심에 찾아본 트리이다. 한번도 사용해 보지 못한 enum을 사용하고 이름도 독특해서 레드블랙 트리를 공부해 보기로 했다.

Introduction to Algorithms 을 참고하였다.

Tree 02. AVL Tree(Adel'son-Vel'skii & Landis, AVL 트리)

MIT introduction to Algorithm (6.006) Lecture 6을 기반으로 정리한 내용입니다.

BST의 문제점

BST에서 Unbalanced tree가 만들어지는 경우, 시간복잡도가 너무 커져서 의미가 없었다. 하지만 Balanced를 유지한다면, 시간복잡도 $O(h)$ 는 안정적이게 $O(lgn)$ 가 될 것이다.(원소의 개수가 n개이고, 한번 내려갈 때마다 2번씩 나뉘면 $log_2n$ 번 내려갔을때 끝까지 내려가므로)

Tree 01. BST(Binary Search Tree, 이진 탐색 트리)

MIT introduction to Algorithm (6.006) Lecture 5를 기반으로 정리한 내용입니다.

Runway Reservation Problem

공항에서 비행기들의 착륙 예정 시간을 생각해보자.

비행기에서 요청한 예정 시간을 $t$ 라 하고, $t$ 로부터 $k$ 시간 내에 다른 착륙 요청이 없다면 $t$ 를 집합 $R$ 에 추가한다. 만약 비행기가 착륙하고 나면 $t$ 를 $R$ 에서 제외한다.