Data Structure & Algorithm

이번 글은 스택에 대해 살펴보도록 하겠습니다.C++ 코드는 이곳에서 확인할 수 있습니다.스택은 LIFO (Last In First Out)을 수행하는 자료구조입니다. 스택은 Push, Pop 메소드를 이용하는 단순한 자료구조입니다. 스택의 동작은 아래 그림과 같으며,

지난 글에서 Stack의 자료구조와 메소드에 대해서 살펴봤습니다. 이번 글에서는 Stack이 어디에 어떠한 방식으로 사용되는지 살펴보도록 하겠습니다. Stack은 워낙 기초적이지만 응용할 곳이 많지만, 제가 알고있는 것을 위주로 작성해보겠습니다. Procedure C

이번 글은 queue에 대해서 살펴보겠습니다.C++ 코드는 이곳에서 확인할 수 있습니다.Queue는 FIFO (First In First Out) 방식의 자료구조입니다. 먼저 삽입된 데이터가 먼저 나오는 구조이고, 자료구조를 그림으로 표현하면 아래와 같습니다.Queue

이번 글에서는 Linked List를 다뤄보겠습니다.C++ 코드는 이곳에서 확인할 수 있습니다.이전 글에서 queue에 대해서 살펴봤는데, linked list와 차이점을 살펴보자면 다음과 같습니다. Queue는 enque/dequeue operation만을 지원하기

$T(n)=aT(n/b) + f(n)$여기에서 "$n/b$"는 $\\lceil{n/b}\\rceil$ 혹은 $\\lfloor{n/b}\\rfloor$를 의미함.$(a\\geq1, b>1, and\\ f(n) > 0)$$f(n)=O(n^{log_b a-\\epsilon}

이번 글에서는 divide & conqure를 더 깊이있게 살펴보기 위해서 matrix multiplaction (이하 matmul)에 대한 알고리즘을 살펴보고자한다. Matmul은 단순히 입력 matrix의 scalar multiplcation & summation을

하... 실수로 작성했던 글이 날아가버렸...네요.Merge sort에 대한 핵심적인 그림은 위와 같습니다. Sorting을 하는데 array를 원본그대로(in-place) sorting 하는게 아니라 작은 단위로 쪼개서 작은 array부터 sorting 하는 알고리즘

이번 글에서는 Hashing에 대해 다뤄보고자 합니다.본 글에서 다루는 코드는 이곳에서 살펴볼 수 있습니다.Hashing algorithm을 사용하여 hash table data structure를 구성하는 경우, 핵심적인 method는 insert, search, d

Heap이란, complete binary tree를 기본으로 하는 자료구조이며, 다음의 heap property를 만족시킵니다.Root를 제외한 모든 node의 index i에 대해서 $APARENT(i)\\ge Ai$를 만족해야함.A\[1]이 tree의 root임을

Sorting Characteristics | Algorithm | Comparison | In-place | Stable | Worst-case | Average-case | | :-: | :-: | :-: | :-: | :-: | :-: | | Insertion s

Insertion sort는 sorting algorithm 중 단순한 알고리즘에 속하고, 이해하기에도 직관적이지만 그만큼 복잡도가 커지는 알고리즘입니다.이번 글부터 기본 알고리즘에 대한 코드는 $ChatGPT$의 도움을 받아서 작성할 예정입니다.단순하고 반복적인 알고

Quick sort는 배열을 분할하고, 각각의 부분 배열을 정렬하는 divide and conquer 방식의 정렬 알고리즘입니다. 이 알고리즘의 핵심은 pivot을 선택하는 것입니다. Pivot은 배열의 아이템 중 하나로 선택되며, 이를 기준으로 나머지 아이템을 분할합

그래프(Graph)는 여러 개의 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성된 자료구조이다. 그래프는 현실 세계에서의 여러 현상을 표현할 수 있으며, 다양한 문제들을 그래프로 모델링하여 해결할 수 있다. 여기서는 그래프의 종류, 특징 및 장단점, 복

BFS(너비 우선 탐색)는 그래프 자료구조에서 사용되는 탐색 방법 중 하나입니다. 시작점으로부터 거리가 가까운 정점부터 먼저 탐색하는 방법입니다. 일반적으로 큐(Queue)를 이용하여 구현합니다.BFS는 그래프의 최단 거리를 구하는 문제에서 매우 유용하게 사용됩니다.

Binary search tree(BST)는 이진 트리의 일종으로, 모든 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 현재 노드보다 작은 값을, 오른쪽 자식 노드는 현재 노드보다 큰 값을 가지는 트리 자료구조이다. 이러한 특성으로 인해 탐색, 삽입, 삭

Red-black tree(레드블랙 트리)는 self-balancing binary search tree(자가 균형 이진 탐색 트리) 중 하나입니다.