Data Structures8 [Data Structures] Hash Table (해시 테이블) HashingHashing은 데이터의 삽입, 삭제, 조회를 상수 시간에 수행하기 위해 사용되는 기술이다. Hash TableHash Table은 Key와 Value를 포함하는 고정된 길이의 배열이다. Hash FunctionHash function은 각각의 Key를 Hash Table의 특정 셀에 맵핑한다. 이는 가능한 계산하기 간단해야 하며, Collision(충돌, 후술 할 것)을 최소화 하도록 설계되는 것이 좋다. 또한 Hash Function의 값은 Uniform한 분포를 따라야 한다. Implementation of Simple Hash Table주민번호가 key이고 주민 객체가 value인 간단한 Hash Table을 구현할 것이다.다음은 Person의 ADT와 구현체이다.#define STR.. 2024. 8. 15. [Data Structures] Heap (힙) Priority Queue (우선순위 큐) 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료 구조이다. 우선 순위 큐는 배열이나 연결 리스트로 구현할 수 있지만 데이터의 수가 많아지면 노드의 수에 비례해서 성능이 저하되기 때문에 가장 좋은 성능을 이끌어 내기 위한 힙이라는 자료구조를 사용한다. Heap (힙) 힙은 완전 이진 트리이다. Max Heap(최대 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같고, Min Heap(최소 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 작거나 같다. - 이진 힙의 구조 힙은 완전 이진 트리 이기 때문에 원소가 배열에 저장된다. - Insertion 원소를 삽입할 때에는 트리 마지막에 삽입을 .. 2024. 8. 6. [Data Structures] AVL Tree (AVL 트리) AVL Tree일반적인 이진탐색 트리의 경우 노드가 한 방향으로 쏠릴 경우 연결리스트와 동일해져 이진 탐색 트리의 장점을 잃게 된다. 이를 개선하기 위해 트리의 균형을 유지하는 트리가 AVL 트리이다. Balance FactorAVL 트리에서는 균형의 정도를 표현하기 위해 Balance Factor라는 것을 사용하는데 이는 왼쪽 서브 트리와 오른쪽 서브 트리의 height의 차이로 계산된다. LL 회전Balance Factor가 2인 노드가 있을 때, 그 노드의 왼쪽 자식 노드의 왼쪽 서브트리에 노드가 추가된 경우를 LL 상태라고 한다. 이러한 경우에는 LL 회전을 통해 트리의 균형을 맞춘다.LL 회전을 일반화 하면 다음과 같다.서브 트리 x 왼쪽에 노드가 추가된다면 LL회전을 수행하게 된다. 이때 k.. 2024. 7. 31. [Data Structrues] Binary Search Tree (이진 탐색 트리) Binary Search Tree이진 탐색은 탐색에 소요되는 시간복잡도가 O(logN)이지만 자료구조가 아니므로 삽입 및 삭제가 불가능하다. 연결 리스트는 삽입 및 삭제의 시간복잡도는 O(1)이지만, 탐색하는데 소요되는 시간복잡도가 O(N)이다. 이 두가지를 결합하여 두 장점을 모두 얻는 것이 이진탐색트리이다.특징은 다음과 같다.- 각 노드의 자식이 2개 이하이다. (이진 트리)- 각 노드의 왼쪽 서브트리에 있는 노드들은 부모 노드보다 작고, 오른쪽 서브트리에 있는 노드들은 부모 노드보다 크다.- 중복된 노드가 없다. (검색 속도를 느리게 하지 않기 위해서)- 중위 순회 방식으로 정렬된 순서를 읽을 수 있다. (왼쪽 - 루트 - 오른쪽) SearchingcNode : 현재 노드target cNode =.. 2024. 7. 20. [Data Structures] Tree (트리) Tree트리는 사이클 없이 간선으로 연결되어있는 노드들의 집합이다. Siblings한 노드의 자식 노드들은 서로 Sibling이라고 한다. Ordered Tree각 레벨에 있는 자식 노드들 사이의 순서에 의미가 부여되어 있는 트리 Degree노드의 Degree는 해당 노드가 갖고 있는 자식 노드의 수이고, 트리의 Degree는 트리의 노드들의 Degree중 최댓값을 의미한다. leaf 노드는 Degree가 0이다. Path, Length of path한 노드에서 다른 노드까지의 경로 상에 존재하는 노드들의 순서를 path 라고하고, 그 노드들을 연결하는 간선의 개수를 length of a path라고 한다. Depth(level) of a node트리의 루트 노드부터 특정 노드까지의 length of t.. 2024. 7. 15. [Data Structures] Stack and Queue (스택과 큐) Stack입력과 출력이 한 곳(Top)에서만 발생하는 자료구조이다.LIFO(Last In First Out) : 가장 나중에 들어간 것이 가장 먼저 나온다.함수의 콜 스택, DFS 등에서 사용된다. 다음은 스택의 ADT이다.struct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;typedef int ElementType;typedef int bool;struct Node{ ElementType Element; PtrToNode Next;};Stack CreateStack();bool isEmpty(Stack);void MakeEmpty(Stack);void Push(ElementType, Stack);ElementType Top(.. 2024. 7. 11. 이전 1 2 다음
