Algorithm

Data Structure

Stack

C++


void init(Stack *s) { s->top = -1;}

bool empty(Stack *s) {
    if (s->top == -1) return true;
    return false;
}

bool full(Stack *s) { 
    if (s->top == MAX_SIZE -1) return true;
    return false;
}

void push(Stack *s, element item) {
    if (full(s)) {
        cout << "Stack is saturated";
        return;
    }
    s->top += 1;
    s->array[s->top] = item;
}

void pop(Stack *s) {
    if (empty(s)) {
        cout << "Stack is empty";
        return;
    }
    s->top -= 1;
}

Code copied! :)

Stack Implementation in C++
Basic LIFO Data Structure

A stack is a data structure that allows adding and removing elements only from one end, known as the top of the stack. The last element added is the first one to be removed, following the Last In, First Out (LIFO) principle. The time complexity for both push and pop operations is O(1).

Push Process

1. Push "Element 1"

2. Push "Element 2"

3. Push "Element 3"

Element 3

Element 2

Element 1

Queue

C++


typedef int element;
typedef struct {
    int front;
    int rear;
    element array[MAX_SIZE];
} Queue;

void init(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool empty(Queue *q) {
    if (q->front == q->rear) return true;
    return false;
}

bool full(Queue *q) { 
    if (q->rear == MAX_SIZE - 1) return true;
    return false;
}

void enqueue(Queue *q, element item) {
    if (full(q)) {
        cout << "Queue is saturated\n";
        return;
    }
    q->array[++q->rear] = item;
}

void dequeue(Queue *q) {
    if (empty(q)) {
        cout << "Queue is empty";
        return;
    }
    int result = q->array[++q->front];
    cout << result << " was removed\n";
}

Code copied! :)

Queue Implementation in C++
FIFO Data Structure

A queue is a data structure that allows elements to be added at the rear and removed from the front. It follows the First In, First Out (FIFO) principle, ensuring the order of elements as they were inserted. The time complexity for both enqueue and dequeue operations is O(1).

Enqueue Process

1. Enqueue "Element 1"

2. Enqueue "Element 2"

3. Enqueue "Element 3"

Deque

C++


void init(Deque *dq) { dq->front = dq->rear = 0; }

bool empty(Deque *dq) {
    if (dq->front == dq->rear) return true;
    return false;
}

bool full(Deque *dq) {
    if( (dq->rear + 1) % MAX_SIZE == dq->front) return true;
    return false;
}

// append-rear
void append(Deque *dq, element item) {
    if(full(dq)) return;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
    dq->array[dq->rear] = item;
}

// append-front
void appendleft(Deque *dq, element item) {
    if(full(dq)) return ;
    
    dq->array[dq->front] = item;
    dq->front = ((dq->front - 1)+ MAX_SIZE) % MAX_SIZE;
}

// pop-rear
void pop(Deque *dq) {
    if(empty(dq)) return;
    
    cout << dq->array[dq->rear]<<" was removed\n";
    
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
}

// pop-front
void popleft(Deque *dq) {
    if(empty(dq)) return;

    dq->front = (dq->front + 1) % MAX_SIZE;
    int result = dq->array[dq->front];
    cout << result << " was removed\n";
}

Code copied! :)

Deque Implementation in C++
Double-Ended Queue

A deque (double-ended queue) allows insertion and removal of elements from both the front and rear ends, providing a flexible data structure.
The time complexity for all operations (append, append left, pop, and pop left) is O(1).

Deque Operations

1. Append to Rear "A"

2. Append to Front "B"

3. Append to Rear "C"

4. Pop from Front (Remove "B")

5. Pop from Rear (Remove "C")

Priority Queue

C++


template 
class priority_queue {
private:
    int cnt; // number of elements in priority_queue
    T heap[MAX_N];

public:
    int size() { return cnt; }

    priority_queue() { cnt = 0; } // init

    void swap(int aIdx, int bIdx) {
        int temp = heap[aIdx];
        heap[aIdx] = heap[bIdx];
        heap[bIdx] = temp;
    }

    void push(T item) {
        heap[++cnt] = item;
        int cur = cnt;

        while (cur > 1) {
            int par = cur >> 1;
            if (heap[cur] < heap[par]) break;
            swap(cur, par);
            cur = par;
        }
    }

    void pop() { 
        heap[1] = heap[cnt--];
        int cur = 1;

        while (cur <= cnt) {
            int left = (cur << 1) <= cnt ? 
                       (cur << 1) : -1;
            int right = (cur << 1 | 1) <= cnt ?
                        (cur << 1 | 1) : -1;
            int child = cur;

            if (left == -1) break;
            if (heap[cur] < heap[left]) child = left;
            if (right != -1 && heap[child] < heap[right]) 
                child = right;

            if (child == left) {
                swap(cur, left);
                cur = left;
            } 
            else if (child == right) {
                swap(cur, right);
                cur = right;
            } else break;
        }
    }

    T top() { return heap[1]; }

    bool empty() { return cnt == 0; }
};

Code copied! :)

Priority Queue Implementation in C++

This implementation of a priority queue uses a binary heap to efficiently manage elements.

Time Complexity: - Insertion (push): O(log n)
- Removal (pop): O(log n)
- Access (top): O(1)

Priority Queue Implementation

This Priority Queue implementation is based on a Binary Heap. A heap is a complete binary tree structure where each parent node is always greater than its child nodes (in the case of a max-heap).

push Function

When a new element is inserted, it is added to the last position of the heap. Then, it is compared with its parent node, and the upheap process is performed to maintain the heap property.

pop Function

The top element of the heap is removed, and the last element is moved to the top. Then, it is compared with its child nodes, and the downheap process is performed to maintain the heap property.

Circular Queue

C++


void init(Queue *q) { 
    q->front = q->rear = 0;
}

bool empty(Queue *q) {
    if(q->front == q->rear) return true;
    return false;
}

bool full(Queue *q) {
    if ((q->rear + 1) % MAX_SIZE == q->front) return true;
    return false;
}

void enqueue(Queue *q, element item) {
    if (full(q)) {
        cout <<"Queue is saturated \n";
        return;
    }
    // maintaining the shape of a circular queue
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->array[q->rear] = item;
}

void dequeue(Queue *q) {
    if(empty(q)) {
        cout << "Queue is empty";
        return;
    }
    
    q->front = (q->front + 1) % MAX_SIZE;
    int result = q->array[q->front];
    cout<< result<< " was removed\n";
}

Code copied! :)

Circular Queue Implementation in C++
FIFO with Wrap Around

A circular queue is an advanced version of a regular queue where the end of the queue wraps around to the beginning, forming a circle. This C++ implementation ensures efficient use of space, allowing the queue to be reused without shifting elements. The time complexity for both enqueue and dequeue operations is O(1).

Enqueue and Dequeue Process

1. Enqueue "A", "B", "C"

2. Dequeue (Remove "A")

3. Enqueue "D"

Doubly Linked List

C++


typedef int element;

typedef struct Node {
    element data;
    struct Node *next, *prev;
} Node;

Node* makeNode(element item) {
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->data = item;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void insert_left(Node* head, element item) {
    Node* p = makeNode(item);
    p->next = head->next;
    head->next = p;
    p->prev = head;
}

void insert_right(Node* head, element item) {
    Node *newNode = makeNode(item);
    Node *cur = head;
    while (cur->next) cur = cur->next;
    cur->next = newNode;
    newNode->prev = cur;
}

void pop_left(Node* cur) {
    Node* temp = cur;
    cur->prev->next = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    free(temp);
}

void pop_right(Node *head) {
    Node *cur = head, *temp;
    while (cur->next) cur = cur->next;
    temp = cur;
    if (cur->prev) cur->prev->next = NULL;
    free(temp);
}

Code copied! :)

Doubly Linked List Implementation in C++
Linear Data Structure with Two Pointers

A doubly linked list is a linear data structure where each element, or node, points to both its previous and next node, allowing bidirectional traversal.
Time Complexity:
- Insertion at the beginning (insert_left): O(1)
- Insertion at the end (insert_right): O(n)
- Removal from the beginning (pop_left): O(1)
- Removal from the end (pop_right): O(n)

Doubly Linked List Operations

1. insert_left "A"

2. insert_right "B"

3. insert_left "C"

4. pop_left (Remove "C")

5. pop_right (Remove "B")

HashMap

C++


size_t djb2(const char* str) {
    // str = "blue"
    size_t hash = 5381;

    for(; *str; ++str) {
        hash = ((hash << 5) + hash) + *str;
    }

    return hash;
}

const int MAX_N = 1e4 + 4;
const int MAX_LEN = 5e2 + 5;

typedef struct Node {
    char str[MAX_LEN]; // key
    Node* next;
} Node;

// Memory Pool Technique
int node_count;
Node nodes[MAX_N];

Node* new_node(const char str[MAX_LEN]) {
    strcpy(nodes[node_count].str, str);
    nodes[node_count].next = NULL;

    return &nodes[node_count++];
}

class HashMap {
    static constexpr size_t TABLE_SIZE = 1 << 12;
    static constexpr size_t DIV = TABLE_SIZE - 1;

    Node hash_table[TABLE_SIZE];

public:
    HashMap() {}

    void init() {
        memset(hash_table, 0, sizeof(hash_table));
        node_count = 0;
    }

    void insert(const char str[MAX_LEN]) {
        Node* prev_node = get_prev_node(str);

        if(prev_node->next == NULL) {
            prev_node->next = new_node(str);
        }
    }

    void remove(const char str[MAX_LEN]) {
        Node* prev_node = get_prev_node(str);

        if(prev_node->next != NULL) {
            prev_node->next = prev_node->next->next;
        }
    }

    Node* get(const char str[MAX_LEN]) {
        return get_prev_node(str)->next;
    }

private:
    Node* get_prev_node(const char str[MAX_LEN]) {
        Node* prev_ptr = &hash_table[djb2(str) & DIV];

        while(prev_ptr->next != NULL &&
              strcmp(prev_ptr->next->str, str) != 0) {
            prev_ptr = prev_ptr->next;
        }

        return prev_ptr;
    }
};

Code copied! :)

HashMap Implementation in C++
Using djb2 Hash Function and Memory Pool Technique

This HashMap uses the djb2 hash function to hash strings to integer values, which are then used to store and retrieve values from a hash table.

djb2 Hash Function
The djb2 hash function calculates the hash value by iterating over each character of the string and performing the calculation:
hash = hash * 33 + c;
Where hash * 33 is computed as (hash << 5) + hash. This allows the hash value to be updated efficiently by using bit-shifting operations. This method is efficient and provides a good distribution of hash values for strings.

Memory Pool Technique
To optimize memory allocation, we use a memory pool technique. Instead of dynamically allocating memory for each node, a fixed array of nodes is allocated at the start. This allows us to quickly allocate new nodes from this pre-allocated pool, reducing the overhead of frequent memory allocations.

HashMap Simulation

1. Insert "blue" using Memory Pool

Index 7

"blue" → djb2("blue") = 5381

Node 0: "blue"

Node 1: (free)

Node 2: (free)

2. Insert "green"

Index 3

"green" → djb2("green") = 6349

Node 0: "blue"

Node 1: "green"

Node 2: (free)

3. Retrieve "blue"

Index 7

Found "blue"

Tree

Binary Tree

C++


typedef int element;

typedef struct Node {
    element data;
    struct Node *left, *right;
} Node;

Node* makeNode(element item) {
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->data = item;
    
    return newNode;
}

void fillTree(Node* root, Node* l, Node* r) {
    root->left = l;
    root->right = r;
}

void preorder(Node *root) {
    if(root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(Node *root) {
    if(root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void postorder(Node *root) {
    if(root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

Code copied! :)

Binary Tree Implementation in C++
Tree Data Structure with Recursive Traversal

A binary tree is a tree data structure where each node has at most two children, referred to as the left and right child. In this implementation, we define a binary tree node and three types of tree traversal methods:

Preorder Traversal: Visit the root node first, then traverse the left subtree, followed by the right subtree.
Inorder Traversal: Traverse the left subtree first, visit the root node, and then traverse the right subtree.
Postorder Traversal: Traverse the left subtree, then the right subtree, and visit the root node last.

Binary Tree Traversal Visualization

Preorder: 1, 2, 4, 5, 3, 6, 7
Inorder: 4, 2, 5, 1, 6, 3, 7
Postorder: 4, 5, 2, 6, 7, 3, 1

Prim MST

C++


vector adj[MAX_V];

int prim(vector& selected) {
    selected.clear();
    vector added(V, false);

    vector minWeight(V, INF), parent(V, -1);

    int ret = 0; // sum of weight

    minWeight[0] = 0; // Starting Node
    parent[0] = 0;

    for (int iter = 0; iter < V; ++iter) {
        int u = -1;
        for (int v = 0; v < V; ++v) {
            if ((!added[v]) && 
                (u == -1 || minWeight[v] < minWeight[u])) 
                u = v;
        }   
        printf("iter: %d | u: %d\n", iter, u);

        if (u == -1) break; 

        if (parent[u] != u) 
            selected.push_back({parent[u], u});
        
        ret += minWeight[u];
        added[u] = true;

        // check all adjacent edges
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int weight = adj[u][i].second;
            if (!added[v] && minWeight[v] > weight) {
                parent[v] = u;
                minWeight[v] = weight;
            }
        }
    }
    return ret;
}

Code copied! :)

1. Prim Algorithm

This algorithm starts from the starting vertex and expands the spanning tree set step by step.
The frame is expanded by selecting the vertex connected to the lowest edge among adjacent vertices.

2. Difference between Kruskal

Kruskal's algorithm is an edge-based algorithm, while Prim's algorithm is a vertex-based algorithm.

3. Logic

Step 1) Algorithm selects the vertex u that
has not yet been included in MST and has the smallest edge weight connecting it to the MST.
Step 2) Once u is chosen, it is marked as added to the MST by setting added[u] to true, and the minimum weight minWeight[u] is accumulated into the total cost ret.
Step 3) The algorithm then inspects all adjacent vertices v of the chosen vertex u.
Step 4) If an adjacent vertex v is not part of the MST and the edge's (u-v) weight is smaller than the current recorded minimum weight minWeight[v], the algorithm updates minWeight[v].

4. Time Complexity

- O(n²) with an array
- O(m log n) with a binary heap

Kruskal MST

C++


typedef pair<int, int> pii;
typedef pair<int, pii> ippi;

// Find function for union-find
int find(int x) {
    if (par[x] < 0) return x;
    return par[x] = find(par[x]);
}

// Union function for union-find
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (arr[a] < arr[b]) par[b] = a;
    else par[a] = b;
}

// Kruskal's algorithm to find MST
int kruskal(vector &edges, int n) {
    // Sort edges by weight
    sort(edges.begin(), edges.end());
    
    memset(par, -1, sizeof(par));

    int mst_cost = 0;

    for (auto &edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        // If u and v are not connected
        if (find(u) != find(v)) {
            merge(u, v); // Merge u and v
            // Add edge weight to MST cost
            mst_cost += weight; 
        }
    }

    return mst_cost;
}

Code copied! :)

Kruskal's Minimum Spanning Tree (MST)

1. Greedy Method

- Always need to verify that it provides the optimal answer.

2. Logic

Step 1) Sort graph edges in ascending order of weight.
Step 2) Find edges that do not form a cycle in the sorted list of edges and add them to the current MST set.
Step 3) If it forms a cycle, the edge is excluded.

Example - Important Part

Edge dg: This edge won't be added because this edge makes a cycle.
Termination: After selecting edge (e, f),
the number of edges will be 6, which is equal to
(# of nodes - 1), thus the algorithm will terminate.

3. How to Find a Cycle: Union Find

4. Complexity

Space: |E|
Time: |E|log(|E|)

Lowest Common Ancestor (LCA)

C++


const int MAX_N = 5e4 + 4;
// 2^x + 2^(x-1) + 2^(x-2) >= 50000
const int MAX_B = 16;       

vector adj[MAX_N];
int n, m, ST[MAX_N][MAX_B], dep[MAX_N];

void makeTree(int cur, int par) {
    for(int child : adj[cur]) {
        // Don't search node that
        // is adjacent but parent-related
        if(child == par) continue;
        
        ST[child][0] = cur;
        dep[child] = dep[cur] + 1;
        
        // Configure trees with adjacent nodes
        makeTree(child, cur);
    }
}

int lca(int u, int v) {
    // Desired situation: dep[u] > dep[v]
    // Control of situation as desired
    if(dep[u] < dep[v]) return lca(v, u);

    int diff = dep[u] - dep[v];

    // Move node as high as possible
    for(int i=MAX_B-1; diff && i>=0; --i) {
        if((1 << i) <= diff) {
            u = ST[u][i];
            diff -= (1 << i);
        }
    }
    
    if(u == v) return u;

    // The height of vertex u and
    //that of vertex v are the same
    for(int i = MAX_B - 1; i >= 0; --i) {
        // Two nodes belong to different component
        if(ST[u][i] != ST[v][i]) {
            u = ST[u][i];
            v = ST[v][i];
        }
    }

    return ST[u][0];
}

Code copied! :)

Lowest Common Ancestor (LCA) in C++
Using Binary Lifting and Sparse Table

The LCA algorithm finds the lowest common ancestor of two nodes in a tree. This implementation uses the binary lifting method to preprocess the tree, allowing for efficient LCA queries in O(log n) time.

- makeTree: Constructs the tree and initializes the sparse table for binary lifting.
- lca: Finds the LCA of two nodes u and v by moving them up to the same level and then to their common ancestor.

LCA Visualization

LCA(4, 5): 2
LCA(4, 6): 1
LCA(3, 4): 1

Trie

Python


class Trie:
    def __init__(self):
        # Key: number, Value: Trie
        self.child = {} 
        self.finished = False

    def insert(self, phone):
        node = self
        for digit in phone:
            # Operate when there's no targeted number
            if digit not in node.child:         
                node.child[digit] = Trie()     

             # Move to next dictionary (Trie)
            node = node.child[digit]           

        # Inform the end of trie
        node.finished = True                    

    def search(self):
        rst = True
        for cur_node in self.child.values():
            if cur_node.finished:
                if len(cur_node.child):
                    return False
                else:
                    return True

            # If anyone is false, the result is false
            temp = cur_node.search()
            if temp is False:
                rst = False

        # Check for all cases
        # Prevent one trie from being a subset of another trie
        # Trie 1) 1-2-3-4: 4(end)
        # Trie 2) 1-2-3-4-5-6-7: 7(end)
        # Trie 2 passes Trie 1's end
        return rst

Code copied! :)

Trie Implementation in Python
Preventing Subset Prefix Issue

A Trie is a tree-like data structure used to efficiently store and search a dynamic set of strings. In this implementation, we use a Trie to store phone numbers and ensure that no number is a prefix of another.

- insert: Inserts a phone number into the Trie.
- search: Checks if any phone number is a prefix of another number, ensuring no subset relationship exists.

Trie Subset Prefix Visualization

Inserted Numbers: 1234, 1234567
Is Prefix Found?: Yes, "1234" is a prefix of "1234567"

Journey of Algorithm

1. CS Algorithm Template

Data Structure

Stack

Stack Implementation in C++ Basic LIFO Data Structure

Push Process

Queue

Queue Implementation in C++ FIFO Data Structure

Enqueue Process

Deque

Deque Implementation in C++ Double-Ended Queue

Deque Operations

Priority Queue

Priority Queue Implementation in C++

Priority Queue Implementation

push Function

pop Function

Circular Queue

Circular Queue Implementation in C++ FIFO with Wrap Around

Enqueue and Dequeue Process

Doubly Linked List

Doubly Linked List Implementation in C++ Linear Data Structure with Two Pointers

Doubly Linked List Operations

HashMap

HashMap Implementation in C++ Using djb2 Hash Function and Memory Pool Technique

HashMap Simulation

Tree

Binary Tree

Binary Tree Implementation in C++ Tree Data Structure with Recursive Traversal

Binary Tree Traversal Visualization

Prim MST

1. Prim Algorithm

2. Difference between Kruskal

3. Logic

4. Time Complexity

Kruskal MST

Kruskal's Minimum Spanning Tree (MST)

1. Greedy Method

2. Logic

Example - Important Part

3. How to Find a Cycle: Union Find

4. Complexity

Lowest Common Ancestor (LCA)

Lowest Common Ancestor (LCA) in C++ Using Binary Lifting and Sparse Table

LCA Visualization

Trie

Trie Implementation in Python Preventing Subset Prefix Issue

Trie Subset Prefix Visualization

2. Machine Learning Algorithm Template

3. LeetCode

4. BOJ

Stack Implementation in C++
Basic LIFO Data Structure

Queue Implementation in C++
FIFO Data Structure

Deque Implementation in C++
Double-Ended Queue

Circular Queue Implementation in C++
FIFO with Wrap Around

Doubly Linked List Implementation in C++
Linear Data Structure with Two Pointers

HashMap Implementation in C++
Using djb2 Hash Function and Memory Pool Technique

Binary Tree Implementation in C++
Tree Data Structure with Recursive Traversal

Lowest Common Ancestor (LCA) in C++
Using Binary Lifting and Sparse Table

Trie Implementation in Python
Preventing Subset Prefix Issue