Leo's notes

Conceptdisjoint set을 효과적으로 표현할 수 있는 트리형 자료구조같은 set에 포함된 원소들은 같은 root를 가진다Example#include #include typedef struct _element { struct _element *parent;} Element; Element *make_element() { Element *element = (Element *)malloc(sizeof(Element)); element->parent = element; return element;} Element *get_root(Element *element) { Element *cur = element; while(cur->parent != cur) { cur = cur->parent; } ele..

Example#include #include typedef struct _stack { int *stack; int top; int size;} Stack; Stack *newStack(int size) { Stack *stack = (Stack *)malloc(sizeof(Stack)); int *arr = (int *)malloc(sizeof(int)*size); stack->stack = arr; stack->top = -1; stack->size = size; return stack;} void push(Stack *stack, int value) { if(stack->size == stack->top) { stack->stack = (int *)realloc(stack->stack, sizeof..

Concept그래프의 인접리스트를 2차원 배열, 2차원 연결리스트, 또는 해시테이블과 연결리스트로 등으로 구현할 수 있음Example2차원 연결리스트의 구현의 경우#include #include typedef struct _vertex { struct _vertex *next; struct _vertex *adjacent; int number;} Vertex; typedef struct _graph { Vertex *head;} Graph; Vertex *newVertex() { Vertex *vertex = (Vertex *) malloc(sizeof(Vertex)); vertex->number = -1; vertex->next = NULL; vertex->adjacent = NULL; return v..

Time ComplexityWorst CaseSearch : O(n) Insertion : Access 후에도 삽입지점까지 최대 n번 이동해야 함 - O(n)Deletion : Access 후에도 삭제지점까지 최대 n번 이동해야 함 - O(n)Average CaseSearch : Theta(1)Insertion : Theta(1)Deletion : Theta(1)Space ComplexityWorst CaseO(n)Example#include #include #include #define HASH_SIZE 10 typedef struct _node { struct _node *next; char *value;} Node; typedef struct _hashTable { Node *table[HASH_S..

Example#include #include typedef struct _node { struct _node *child[26]; int end;} Node; Node *createNewNode() { Node *newNode = (Node *) malloc(sizeof(Node)); for(int i=0;ichild[i] = NULL; } newNode->end = 0; return newNode;} void push(Node *node, char *s, int depth) { if(s[depth] == '\0') { node->end = 1; return; } int index = s[depth] - 'a'; if(node->child[index] == NULL) { Node *newNode = cr..

ConceptPriority Queue는 배열, 연결리스트, Heap 등으로 구현할 수 있다.배열이나 연결리스트의 경우 삽입 또는 삭제시 마다 정렬이 필요, O(n) 시간이 걸릴 수 있으므로 Heap으로 구현하는게 효율적이다. Binary Search Tree는 현재 노드 값보다 왼쪽 자식 노드 값이 더 작고 오른쪽 자식 노드 값이 더 큰 자료구조라면Heap은 현재 노드 값이 자식 노드의 값보다 크기만 하면 된다. 삽입은 마지막 노드에서, 삭제는 루트 노드에서 이루어진다.삭제시 두 자식 노드 중 큰 노드와 비교 및 교환을 하면 됨.*삽입을 마지막 노드에서 하는 이유 : 최대한 트리 밸런스 유지 가능? -> 완전 이진 트리가 Heap의 조건!Time ComplexityWorst CaseBalanced Tr..

Concept현재 노드의 값보다 작으면 왼쪽 자식 노드에, 크면 오른쪽 자식 노드에 값을 저장하는 이진 트리연결리스트는 삽입/삭제 시간이 O(1)이지만 탐색 시간이 O(n)으로 느리고 이진탐색은 탐색 시간이 O(log n)이지만 삽입/삭제가 불가능하므로 이 둘을 보완한 자료구조가 BST이다.Time ComplexityWorst Case균형 잡히지 않고 한줄로 늘어진 트리의 경우가 문제가 됨Access : O(n)Search : O(n) Insertion : O(n) Deletion : O(n)Average CaseAccess : O(log n)Search : O(log n) Insertion : O(log n) Deletion : O(log n)Space ComplexityWorst CaseO(n)Exa..

Concept한 쪽에서 Insertion, 다른 한 쪽에서 Deletion이 발생하는 First in first out 자료구조Time ComplexityWorst CaseAccess : 마지막 원소의 경우 노드를 n번 거쳐야 함 - O(n) Search : 마지막 원소를 찾을 경우 노드를 n번 검색해야 함 - O(n) Insertion : 바로 삽입 가능 - O(1)Deletion : 바로 삭제 가능 - O(1)Average CaseAccess : Theta(n) Search : Theta(n) Insertion : Theta(1)Deletion : Theta(1)Space ComplexityWorst CaseO(n)Example#include #include typedef struct _node { ..

Concept단방향에서 Insertion, Deletion 이 발생하는 First in last out 자료구조Time ComplexityWorst CaseAccess : 스택의 바닥에 있는 값까지 n번 움직여야 함 - O(n)Search : 값이 스택의 가장 바닥에 있을 때 n번 움직여야 함 - O(n) Insertion : 바로 push 가능 - O(1) Deletion : 바로 pop 가능 - O(1)Average CaseAccess : Theta(n)Search : Theta(n) Insertion : Theta(1) Deletion : Theta(1)Space ComplexityWorst Casen개의 데이터를 저장할 노드가 n개만큼 필요함 - O(n) Example#include #includ..

Concept연속된 형태의 자료를 저장하는 구조Time ComplexityWorst CaseAccess : head부터 시작해서 마지막에 있는 데이터에 접근하려면 - O(n)Search : head부터 시작해서 마지막에 있는 데이터를 찾으려면 - O(n)Insertion : 노드 앞/뒤에 바로 삽입할 수 있음 - O(1)Deletion : 해당 노드를 바로 삭제할 수 있음 - O(1) Average CaseAccess - Theta(n)Search - Theta(n)Insertion - Theta(1)Deletion - Theta(1) Space Complexityn개의 데이터를 저장할 노드가 n개만큼 필요함 - O(n) Example#include #include ​ typedef struct _nod..