본문 바로가기

Dev.Basic/자료구조&알고리즘

 (11)
[DataStructure] 5. Red-Black Tree 5. Red- Black Tree트리 자료구조 중 Red- Black Tree에 대해서 알아본다. RBT는 BST를 기반으로하는 트리 형식의 자료구조이다. BST(Binary Search Tree)효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다. 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다. 규칙 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. 규칙 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다..
[DataStructure] Graph라는 자료구조에 대해서 정점과 간선의 집합, 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을 비판적으로 바라보자. 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 해야하는..
[DataStructure] hashcode와 HashMap에 대해서 Hash Code와 HashMapHashMap는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Searching 하는데 데이터 고유의 인덱스로 접근하게 되므로 Time Complexity가 O(1)이 되는 것이다. 그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 다시 채우는 작업이 필요없도록 '특별한 알고리즘'을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 추가적인 데이터의 이동이 없다. `특별한 알고리즘`이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해보인..
[Sorting] 5. Non-Comparison Sorting - Counting Sort, Radix Sort 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 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 ..
[Sorting] 4. Heap, Heapify, Heap Sort Heap SortSpace-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n log n) 원리heap 자료구조를 활용할 Sorting 방법에는 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 Sorting을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 heapify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다. Heap 자료구조란?자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값..
[Sorting] 3. Quick Sort Quick SortSpace-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n log n) Sorting기법 중 가장 빠르다고 해서 quick이라는 이름이 붙여졌다. 하지만 Worst Case에서는 시간복잡도가 O(n^2)가 나올 수도 있다. 하지만 constant factor가 작아서 속도가 빠르다. 원리Quick Sort 역시 Divide and Conquer 전략을 사용하여 Sorting이 이루어진다. Divide 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partit..
[Sorting] 2. Merge Sort 2. Merge SortSpace-Complexity = 입력 배열 크기의 보조 메모리를 사용한다. Time-Complexity = O(n log n) 원리기본적인 개념으로는 n개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. Divide and conquer라는, 분할하여 정복한다의 원리인 것이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단 분할(divide)해서 정복했으니 정복(conquer)한 후에는 결합(combine)의 과정을 거쳐야 한다. Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우에는 ( 원소 하나인..

티스토리툴바