CS/Algorithm6 [Algorithm] 6-3. Red-Black Tree 이번 시간에는 balanced search tree 중 하나인 red-black tree에 대해 알아보도록 하겠다. ● Red-Black Tree - red-black tree는 binary search tree로써, 아래의 4가지 조건을 만족한다. ① Root Property : root는 검은색이다. ② External Property : 모든 leaf node들은 검은색이다. ③ Internal Property : 빨간 노드의 자식들은 검은 노드이다. (부모와 자식이 모두 빨간색인 경우는 없다.) ④ Depth Property : 모든 leaf node들은 같은 black depth를 가져야한다. * black depth - 어떤 노드에서 root까지 가는 경로에 있는 black 노드들의 수. - .. 2020. 4. 28. [Algorithm] 6-2. Binary Search Tree 저번 시간에는 어려운 개념인 amortized analysis라는 알고리즘 분석 방법에 대한 내용에 대해 알아보았다. 이번 시간에는 binary search tree, 그 중에서도 Red-Black Tree에 대해 알아보도록 하겠다. ● Binary Search Trees - binary search tree는 주로 dictionary라는 추상 자료형을 표현하기 위해 주로 사용된다. 임의의 key를 가진 원소를 삽입, 삭제, 탐색할 수 있고, 최악수행시간은 O(n)이다. - 하지만 balanced binary search tree일 경우에는 최악수행시간이 O(log(n))일 것이다. - 순서가 있는 집합에서의 key를 가지는 노드를 가진 트리이고, 자식은 최대 2개이다. - 왼쪽 서브트리의 모든 키들은 .. 2020. 4. 28. [Algorithm] 7-1. Graphs and Graph Traversals 이번 시간에는 자료구조 시간에서도 배운 그래프에 대해 알아보도록 하겠다. 그래프가 사용되는 경우와 그래프의 종류에 대해 먼저 알아보도록 하자. ● 그래프가 사용되는 경우 ① Airline Routes (항공 노선) - 도시들을 vertex(정점)으로 표시, 두 도시를 오가는 항공편이 있으면 edge(간선)으로 표시 - SD에서 SAC로 가는 데 비행기를 가장 적게 갈아타는 방법은? → Shortest Path 문제 → SD-SF-SAC 또는 SD-LA-SAC → BFS(너비 우선 탐색) 방법을 사용하면 된다. - SD에서 SAC로 가는 데 비행기를 가장 많이 갈아타는 방법은? → 단, 한 번 들렀던 도시는 다시 방문하지 않는다. → Longest Simple Path (여기에서 simple은 재방문하지 .. 2020. 4. 28. [Algorithm] 2. Data Abstraction and Basic Data Structures 저번 시간까지 알고리즘과 문제를 분석하는 방법에 대해 배웠다. 이번 시간에는 데이터 추상화와 기본 자료구조에 대해 알아보도록 하겠다. ● Abstract Data Type(ADT) - 추상자료형은 어떤 자료구조가 저장해야할 데이터와 기능을 명세한다. - 추상자료형의 구성 요소 ① 구조 : 데이터 구조 선언 ② 기능 : 연산들 정의 - ADT는 클래스로 구분된다. → C++나 자바에서 나오는 클래스가 바로 구현되어있는 형태이다. 클래스에는 변수들, 어떤 데이터로 구성이 되며, 그 클래스의 인스턴스, 객체에 대한 어떤 기능들을 할 수 있을지가 정의되어 있다. - 알고리즘을 설계하고 정확도를 증명하는 것은 ADT의 연산과 세부 사항에 달려있다. - 추상 자료형은 '구현 방법'은 명세되어있지 않다. 그렇기 때문.. 2020. 4. 26. 이전 1 2 다음
