Leo's notes

Time ComplexityO(n logn)Example#include #include int buf[10]; void merge(int *arr, int left, int right) { int mid = (left + right) / 2; int index = left; int l = left; int r = mid+1; while(l

Time ComplexityO(n^2)Example#define SWAP(x, y) do { typeof(x) SWAP = x; x = y; y = SWAP; } while (0) void bubble_sort(int *arr, int size) { for(int i=0;ikey;j--) { arr[j+1] = arr[j]; } arr[j+1] = key; }} void selection_sort(int *arr, int size) { int min; for(int i=0;i

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 { ..