MIT introduction to Algorithm (6.006) Lecture 7을 기반으로 정리한 내용입니다.
데이터를 비교 및 정렬하는 알고리즘을 위한 ADT를 살펴보고, 각 알고리즘의 Lower Bound를 살펴보자. 그리고 적은 양의 정수로 이루어진 데이터에 대하여, $O(n)$ 의 시간복잡도를 지니는 계수 정렬과 기수 정렬에 대해 살펴보자.
More …
이전 게시글에 이어서, Red-Black Tree의 삭제 부분을 알아보는 게시글 입니다. Introduction to Algorithms 책을 참고하였습니다.
정리 하면서도 확실히 이해했다는 생각이 안들어 틀린 부분이 있을 수 있습니다 ㅠㅠ
More …
Red-Black tree는 MIT OCW 강의에서 다루지 않았지만 AVL트리를 공부하다 보니 사실상 AVL트리는 쓰이지 않고 Red-Black Tree나 B-tree, Treaps 같은 구조를 쓴다는 이야기를 듣고 호기심에 찾아본 트리이다. 한번도 사용해 보지 못한 enum
을 사용하고 이름도 독특해서 레드블랙 트리를 공부해 보기로 했다.
Introduction to Algorithms 을 참고하였다.
More …
MIT introduction to Algorithm (6.006) Lecture 6을 기반으로 정리한 내용입니다.
BST의 문제점
BST에서 Unbalanced tree가 만들어지는 경우, 시간복잡도가 너무 커져서 의미가 없었다. 하지만 Balanced를 유지한다면, 시간복잡도 $O(h)$ 는 안정적이게 $O(lgn)$ 가 될 것이다.(원소의 개수가 n개이고, 한번 내려갈 때마다 2번씩 나뉘면 $log_2n$ 번 내려갔을때 끝까지 내려가므로)
More …
MIT introduction to Algorithm (6.006) Lecture 5를 기반으로 정리한 내용입니다.
Runway Reservation Problem
공항에서 비행기들의 착륙 예정 시간을 생각해보자.
비행기에서 요청한 예정 시간을 \(t\) 라 하고, \(t\) 로부터 \(k\) 시간 내에 다른 착륙 요청이 없다면 $t$ 를 집합 $R$ 에 추가한다. 만약 비행기가 착륙하고 나면 $t$ 를 $R$ 에서 제외한다.
More …