2JINISHAPPY 2JINISHAPPY

https://2jinishappy.tistory.com/318 Color를 이용해서 Self-Balancing을 구현하는 Red-Black Tree 자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다 포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙 2jinishappy.tistory.com 이전 글에서 소개한 것 처럼 레드블랙트리는 BST의 탐색/삽입/삭제 시간을 로그 시간에 수행하기 위해 등장했다 삽입 및 삭제 연산은 red-black property를 해칠 수 있기 때문에 balance를 유지하기 위한 Rotation 연산이 필요하다 이 글에서는 탐색/삽입 연산에 대해 설명한다 Search Node in RBT 레드블랙..

AVL Tree AVL 트리는 아래의 성질을 만족하는 BST(Binary Search Tree)의 한 종류다 Tree 상의 모든 Node p에 대해 p의 left subtree와 right subtree의 height 차이가 최대 1을 넘을 수 없다 이러한 성질을 AVL 트리의 Balanced Property라고 하며, 일반적인 BST와 비교했을 때, Search 연산은 완전히 동일하지만 Insert/Delete 연산을 할 때 이 성질이 깨지지 않도록 추가적인 연산을 수행한다 위의 그림에서 12라는 노드를 추가했을 때, 해당 노드를 자손으로 가지는 노드들(4, 8, 15, 10, 12)의 height가 변한다 그리고 노드 15를 봤을 때 왼쪽 서브트리의 height가 2, 오른쪽 서브트리의 height가..

자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다 포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙트리를 정리하려고 한다 레드블랙트리가 무엇인지에 대해 알기 전에, 레드블랙트리가 어디에서 사용되는지에 대해 두 가지를 소개하자면 Java Collection API의 Map Interface 구현체인 HashMap의 Seperate Chaining 구현에서 사용한다. 👉 Key값의 Collision이 발생할 경우 같은 Hash값을 가지는 원소들을 Collection으로 관리하는데, 이 때 원소의 개수가 많아지면 Red-Black 트리를 이용해서 관리하여 연산 시간을 O(log)으로 관리한다 Linux의 기본 스케줄러인 CFS 스..

'두 개의 Stack으로 Queue 자료구조를 구현해주세요' 라는 질문 어디서 많이 보지 않았나요? 그래서 직접 해보았습니다 사실 처음의 아이디어는 이것이엇습니다 👇 더보기 Enqueue 연산: 스택을 두 개로 나누어서 Enqueue 시 Stack 1에 Push한다 👉 일반 스택의 Push연산과 동일하므로 Time Complexity: O(1) Dequeue 연산: 1️⃣ Stack 1의 모든 Element들을 Stack 2로 이동한다 (하나씩 Pop하면서, Pop된 Value를 동시에 Stack 2로 Push한다). - O(N) 2️⃣ Stack 2의 top을 Pop한다. - O(1) 3️⃣ Stack 2의 element들을 다시 1번처럼 Stack 1로 되돌린다. - O(N) 👉 Time Comple..

➕ Hash Table은 java에서의 HashTable API가 아닌 Hash function을 통해 mapping된 value를 저장하는 Table을 뜻함 👇 이전 글 보기 https://2jinishappy.tistory.com/230 빠른 데이터 검색을 위한 Hashing과 Hash Table select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 2jinishappy.tistory.com 서로 다른 key에 대해 hash function으로 변환된 h(x)가 같을 경우, 같은 index에 값을 저장해야 하는 coll..

select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 것이 효과적인지 고민하는 과정에서 해싱의 원리를 찾을 수 있다. 특정 key가 주어졌을 때, 해당 key 값을 가진 record를 찾기 위한 방법으로는 1️⃣ Key를 index로 가진 array로 table 구현 2️⃣ BST 이용 1번은 조회하는 데 O(1)이 소모되는 대신 |max(key)|만큼의 메모리를 요구하기 때문에 실제로 사용하기에는 어렵다. 2번 또한 1번에 비해서는 get, insert의 평균적인 시간이 짧긴 하지만 O(log n)도 수천, 수만개의 re..

DAG는 Topological Sort, Strongly Connected Component 등을 정의할 때 자주 사용되는 자료구조로 사이클이 존재하지 않는 방향 그래프 를 의미한다 DAG를 이해하기 위해 Directed graph G가 cycle이 있다 ↔ G의 DFS Tree가 back edge를 가지고 있다 이러한 성질들은 서로 필요충분조건을 만족한다는 사실을 알 필요가 있다 1️⃣ ⬅ (G의 DFS Tree가 back edge를 가지고 있다면 G에는 cycle이 존재한다) : 그래프 G에서 임의의 정점 u와 v에 대해 back edge(v,u)가 존재한다고 가정한다(위의 그림). 그러면 u ➡ ... ➡ v ➡ u로의 cycle이 존재한다 2️⃣ ➡ (Directed Graph G가 cycle이 ..

이전 글에서 MST의 정의에 대해 다뤘다(2jinishappy.tistory.com/114) 이제 MST를 생성하는데 사용하는 자료구조인 Disjoint Set과 그것을 관리하는 자료구조인 Union Find에 대해 정의하고, 어떤 연산으로 MST를 만들 수 있는지 알아본다 Union Find의 대표적인 연산은 다음과 같다 1️⃣ makeSet(x): 단일 element(disjoint set)로 이루어진 set을 하나 생성한다. 2️⃣ find(x): x가 포함된 set을 return한다. 3️⃣ union(x, y): x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다. Union Find는 vertex set을 directed tree를 이용하여 저장한다. 이 때, tree의 각 n..