[Data Structure] Tree(4) - Red-Black Tree
2024. 6. 2. 15:28
CS/Data Structure
"Red Black Tree"(RB Tree)란 이진 검색 트리의 일종으로 자가 균형 이진 검색 트리(Self-Balancing BST)이다. BST의 경우 평균적으로 $O(logN)$에 동작하지만, 최악의 경우 $O(N)$이 소요된다. 최악의 경우는 균형이 무너져 편향트리가 되었을 때 발생한다. 따라서, 최악의 경우에도 $O(logN)$을 보장하는 자가 균형 이진 검색트리인 AVL, Red-Black Tree를 사용한다. 특징 "Red Black Tree"는 다음과 같은 규칙을 만족하는 BST이다.#1: 모든 노드는 빨간색 혹은 검은색이다. #2: 루트노드는 검은색이다.#3: 리프(NIL)노드는 검은색이다. #4: 빨간색 노드의 자식은 검은색이다. (즉, 2 연속으로 빨간색이 나올 수 없다.)#5: ..
[Data Structure] Tree(3) - AVL Tree
2024. 5. 23. 14:29
CS/Data Structure
"AVL 트리"는 자가 균형(Self-Balancing) 이진 검색 트리로, 좌우 서브 트리의 높이 차이가 1을 유지한다. 만약, 높이 차이가 1 이상이 나게 된다면 스스로 균형을 맞추어 높이 차이 1을 유지한다. 이전 포스팅에서 보았던 이진 검색 트리의 경우에는 최악의 경우 모든 연산의 시간복잡도가 $O(N)$이 되었다. 이는 다음과 같이 편향트리가 될 수 있기 때문이다. 따라서, AVL트리는 자가 균형을 통해 높이차를 1을 유지함으로써, 모든 연산의 평균 최악 모두 $O(logN)$을 보장한다. Balance Factor 이진 트리에서 Balance Factor는 다음과 같이 정의된다. 즉, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. AVL 트리는 BF값이 [-1, 1]범위 ..
[Data Structure] Tree(2) - Binary Search Tree
2024. 5. 17. 23:13
CS/Data Structure
"이진 검색 트리"(Binray Search Tree)는 다음과 같은 성질을 만족하는 이진트리이다. 각 노드에 들어가는 값들은 대소관계를 비교할 수 있다. 노드의 왼쪽 서브트리는 작은 값들을 가진 노드들로 이루어져 있다. 노드의 오른쪽 서브트리는 큰 값들을 가진 노드들로 이루어져 있다. 좌우 서브트리는 각각 위의 2 조건을 만족한다.이러한 특성 때문에 정렬된 이진 트리(Sorted Binary Tree)라고도 부른다. 이진 검색 트리는 검색, 삽입, 삭제 연산들이 평균적으로 $O(logN)$에 동작한다. 해시의 경우, 위의 연산들을 $O(1)$에 제공하지만, 원소 간의 대소관계는 비교할 수 없다. 하지만, 이진 검색 트리의 경우 "5 보다 큰 최초의 원소"와 같은 대소비교 관련 연산을 수행할 수 있다...
[Data Structure] Tree(1)
2024. 5. 12. 15:32
CS/Data Structure
"트리"(Tree) ADT는 계층 구조를 가지는 그래프의 일종으로 비선형 자료구조이다. 그래프의 일종이기 때문에, 노드와 간선으로 이루어져 있다.이때, 각 노드는 하나의 부모 노드만을 가지며, 여러 개의 자식 노드를 가질 수 있다.이러한 계층 구조에 의해 트리에서는 절대로 순환이 발생하지 않는다. 즉, 트리는 각 노드를 한 번씩만 방문했을 때, 절대 순환이 발생하지 않는 연결 그래프이다. 이렇게 최상위의 노드를 루트노드라 부르며, 모든 트리에는 항상 하나만 존재한다. 또한, 트리 구조는 각 노드를 루트 노드로 하여 하위트리로 분류할 수 있으며, 이러한 특성에 의해 재귀적 자료구조라고도 부른다. 루트 노드(root) : 모든 트리에 하나만 존재하며, 부모가 없는 최상위 노드 리프(단말) 노드(leaf)..
[Data Structure] Graph
2024. 5. 6. 13:39
CS/Data Structure
"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 이들을 잇는 선을 "간선"(edge)라 부른다. 즉, 그래프는 유한한 개수의 정점과 간선으로 이루어진 ADT이다. 이러한 그래프 G 를 G = (V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미한다. 정점(노드) : 각 데이터 간선 : 정점들을 잇는 선 인접 정점: 간선에 의해 연결된 정점 (ex. A의 인접 정점은 B,C)차수(degree) : 정점에 연결된 간선의 개수 (ex. A의 차수는 2)이러한 그래프를 순회하는데 사용하는 알고리즘에는 대표적으로 BFS와 DFS가 있다.순회란, 그래프내의 모든 정점을 한번씩 방문하는 것을 말..
[Data Structure] Hash Table(2) - Implementation
2024. 4. 29. 16:10
CS/Data Structure
Swift에서 HashTable을 활용한 자료구조에는 Set과 Dictionary가 존재한다.이 중 Key-Value 쌍으로 데이터를 저장하는 Dictionary를 구현해 보자. 해당 포스팅에선 Dictionary를 Chaing방법과 Open Addressing 2가지 방법으로 모두 구현해 볼 것이다.여기서는 구현에 관해서만 다룰 것이기 때문에, 해시 테이블 이론에 관련한 것들은 이전 포스팅을 참고 바란다.https://seokyoungg.tistory.com/92 [Data Structure] Hash Table(1) - Concept만약 다음과 같은 데이터가 있다고 가정해 보자. 이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 즉, 품목이 인덱스화 될 필요가 있다. 이처럼 k..
[Data Structure] Hash Table(1) - Concept
2024. 4. 20. 17:12
CS/Data Structure
만약 다음과 같은 데이터가 있다고 가정해 보자. 이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 즉, 품목이 인덱스화 될 필요가 있다. 이처럼 key-value를 매핑하는 것이 "해시 테이블(Hash Table) ADT"이다. 해시 테이블 ADT를 자료구조로 구현하기 위해선, key 값을 정수값으로 매핑할 필요가 있다. 이러한 Key값을 해시 테이블의 인덱스로 매핑하는 것이 "해시 함수"(Hash Function)이다. 이때, 해시 함수의 결과값을 해시, 해시 값, 해시 코드라 부른다. 즉, 해시 테이블(Hash Table) ADT를 자료구조로 구현하기 위해 필요한 것이 해시 함수이다. 해시 함수의 결과값인 해시(해시 값, 해시 코드)는 해시테이블의 인덱스가 된다. 이렇게 인덱스를..
[Data Structure] Priority Queue
2024. 4. 15. 14:42
CS/Data Structure
"우선순위 큐"(Priority Queue)는 다음과 같은 2개의 Main Operation을 명세하는 ADT이다.enqueue(push): 원소를 추가한다.dequeue(pop): 우선순위가 높은 원소를 제거한다. 지난 포스팅에서 다루었던 "큐"(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO의 형태라면, "우선순위 큐"(Priority Queue)는 먼저 들어온 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 ADT이다. 흔히들 "우선순위 큐는 Heap이다"라고 생각하는데, 이는 잘못된 오류이다. 우선순위 큐는 ADT일뿐 위에 말한 2개의 Operation만 제공하면 된다. 즉, 스택이 배열, 연결리스트 등으로 다양한 방법으로 구현할 수 있는 것처럼 우선순위 큐도 다양한 방법으로 구현..
[Data Structure] Queue
2024. 4. 13. 16:06
CS/Data Structure
"큐"(Queue)는 선형 자료구조로 2가지 Main Operation을 기본적으로 제공하는 ADT이다. enqueue(push) : 원소를 추가한다. dequeue(pop) : 가장 처음에 추가된 원소를 제거한다. 지난 포스팅에서 다루었던 스택은 프링글스 통과 같이 LIFO로 동작했다. 반면, 큐는 티켓팅을 위해 줄을 서는 것과 같이 가장 먼저 들어간 원소가 가장 먼저 제거되며, 이를 FIFO라 부른다. 큐 역시 위의 사진과 같이 원소의 삽입과 삭제되는 위치가 정해지기 때문에, Restricted Structure라고도 불린다. 이렇게 원소가 삽입되는 곳을 tail, rear, back이라 부르며, 원소가 삭제되는 곳을 head, front라 부른다. 사용 Computer Science에서 큐는 굉장히..
[Data Structure] 자료구조란?
2024. 3. 13. 17:51
CS/Data Structure
"자료구조"(Data Structure)란 데이터에 효율적인 접근을 위한 데이터의 구조, 관리, 저장을 말한다. 정확히 말하면 "자료구조"는 데이터의 모임으로, "데이터 간의 관계"와 "적용할 함수나 명령"을 의미한다. 예를 들어 자료구조 중 Queue를 생각해 보면, 데이터의 저장 및 삭제까지를 정의한다. 프로그래밍에서 적절한 자료구조는 효율적인 알고리즘을 수행할 수 있게 해준다. Queue 자료구조를 사용하면, BFS 알고리즘은 효율적으로 수행할 수 있다. 자료구조의 분류 자료구조는 크게 2가지로 분류된다. 원시 자료구조 (Primitive Data Structure) 복합 자료구조 (Non-Primitive Data Structure) 원시 자료구조 (Pritimitive Data Structure..