::Devlog::

5. Red- Black Tree트리 자료구조 중 Red- Black Tree에 대해서 알아본다. RBT는 BST를 기반으로하는 트리 형식의 자료구조이다. BST(Binary Search Tree)효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다. 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다. 규칙 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. 규칙 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다..

정점과 간선의 집합, Graph 그래프 관련 용어 정리Undirected Graph와 Directed Graph(Digraph)말 그대로 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph라고 한다. Directed Graph(Digraph) V = {1, 2, 3, 4, 5, 6} E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)} (u, v) = vertex u에서 vertex v로 가는 edge Undirected Graph V = {1, 2, 3, 4, 5, 6}E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)} (u, v) = vert..

Sorting Algorithm을 비판적으로 바라보자.#1. 첫번째 의문 quick sort가 가장 좋고 빠르다며, 그래서 이름도 quick sort라며! 그런데 heap sort, merge sort는 왜 존재하며 왜 필요하지?어디에 쓰이고 있길래 살아남은 거지? 세 sorting algorithm(Quick sort, Merge sort, Heap sort)의 expected-Time Complexity는 O(n log n)으로 모두 동일하다. 하지만 Space Complexity는 merge sort만 Sorting하고자 하는 데이터의 크기 만큼이다. 그러면 일단 heap sort는 그렇다치고, 어떻게 Merge Sort가 살아남았을까? 한정된 메모리 상황에서 ‘빅 데이터'를 Sorting 해야하는..

Hash Code와 HashMapHashMap는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Searching 하는데 데이터 고유의 인덱스로 접근하게 되므로 Time Complexity가 O(1)이 되는 것이다. 그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 다시 채우는 작업이 필요없도록 '특별한 알고리즘'을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 추가적인 데이터의 이동이 없다. `특별한 알고리즘`이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해보인..

non - Comparisons Sorting AlgorithmCounting SortSpace Complexity : in-place 알고리즘이 아니다. buffer를 필요로 한다.Time Complexity : O(n + k)Radix Sort에 대해 알아보기 전에 Count Sort에 대해서 먼저 알아보자. Count Sort에서 사용된 알고리즘이 Radix Sort에서 사용된다. 즉 Radix Sort는 Count Sort의 확장판이라고 할 수 있다. Count Sort는 말 그대로 몇 개인지 개수를 세어 정렬하는 방식이다. 정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 만들어진 배열의 index 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 ..