💻 컴퓨터공학/자료구조
그래프 (Graph)
그래프 (Graph)
2021.11.01Graph 그래프(Graph)는 노드와 간선으로 표현된 자료구조입니다. 그래프에서 노드는 정점이라 불리며, 각 정점은 간선으로 연결되어 있습니다. 정점은 도시로, 간선은 도시 간 이동을 위해 연결된 길로 생각하면 이해하기 쉽습니다. 그래프는 다른 자료구조와 달리 현실 세계를 표현하기 좋습니다. 정점과 간선을 도시와 길로 비유할 수 있듯, 이를 바탕으로 현실 세계를 모델링하면 대표적으로 네비게이션과 같은 시스템을 만들 수 있습니다. 만약 현실에서 마주하는 다양한 문제를 해결하고 싶다면, 그래프는 반드시 이해하고 넘어가야 하는 중요한 자료구조 중 하나입니다. 그래프에서는 다음 용어들을 사용합니다. 정점(Vertex): 하나의 노드 간선(Edge): 두 정점을 연결한 선 가중치(Weight): 간선이 가지는 ..
해시 테이블 (Hash Table)
해시 테이블 (Hash Table)
2021.11.01Hash Table 해시 테이블(Hash Table)은 데이터의 해시 값을 키로 사용한 데이터 집합을 말합니다. 해시는 데이터를 새로운 형태로 변환한다는 의미를 가지고 있으며, 주어진 키를 미리 구현한 해시 함수를 통해 변환합니다. 해시 테이블은 해싱 된 키를 통해 데이터에 바로 접근할 수 있으므로, 매우 빠른 탐색 속도를 갖고 있습니다. 해싱 함수에 일반적으로 사용되는 방법은 다음과 같습니다. 나눗셈법: 키 값을 테이블의 사이즈로 나눈 후의 나머지를 주소로 사용하는 방법 자릿수 접기: 문자열 키 값의 자리마다 정해진 아스키 코드를 합친 값을 주소로 사용하는 방법 해시 테이블을 사용할 때는 충돌(Collision)과 클러스터링(Clustering)을 방지해야 합니다. 충돌은 말 그대로 동일한 해시 값이 ..
우선순위 큐 (Priority Queue)
우선순위 큐 (Priority Queue)
2021.10.30Priority Queue 우선순위 큐(Priority Queue)는 요소들이 우선순위를 가지고 있으며, 높은 우선순위를 가진 요소들이 먼저 나올 수 있는 자료구조를 말합니다. 이전 포스트에 소개했던 힙을 그대로 사용하기 때문에, 사실 큐라고 하는 게 맞나 싶긴 하지만, 동작 자체가 큐와 동일하기 때문에 이런 명칭이 붙은 것 같기도 합니다. 힙과의 차이점은 노드에 우선순위를 할당 할 멤버 변수가 추가되었다는 것과 메소드의 이름이 큐에 맞게 변경된 것 말고는 없습니다. 그래도 힙이 선행되는 자료구조이기 때문에 꼭 이해해야 합니다. 그리고 우선순위 큐는 그래프 알고리즘 중 최소 신장 트리를 구성하는 프림 알고리즘과 최단 경로를 찾는 다익스트라 알고리즘 등에 활용할 수 있는 정말 유용한 자료구조입니다. 노드 ..
힙 (Heap)
힙 (Heap)
2021.10.29Heap 🙂 힙(Heap)은 트리 내에서 가장 크거나 작은 값을 루트로 가진 완전 이진 트리를 말합니다. 가장 작은 값이 루트로 오는 경우를 최소힙(Min-Heap)이라 말하며, 반대로 가장 큰 값이 오는 경우는 최대힙(Max-Heap)이라 합니다. 힙은 큐에서 나올 요소에 대해 우선순위를 적용하는 우선순위 큐를 만들 때와 힙을 통한 정렬인 힙 정렬에 활용할 수 있습니다. 루트가 가진 값이 기본적으로 최솟값 또는 최댓값이기 때문에 이런 활용들이 가능한 것입니다. 우선순위 큐는 이후의 포스트를 통해 소개하겠습니다. 힙은 새로운 요소를 추가하거나 제거할 때, 힙을 재구성해야 하므로 리스트보다는 배열로 만드는 편입니다. 노드 & 클래스 생성 function Node(data) { this.data = data..
분리 집합 (Disjoint Set)
분리 집합 (Disjoint Set)
2021.10.26Disjoint Set 🙂 분리 집합(Disjoint Set)은 교집합을 갖지 않는 집합들을 의미합니다. 각 집합은 트리로도 표현이 가능한데, 다만 이 경우에는 자식 노드들이 부모를 가리키는 형태로 구현해야 합니다. 그렇게 하나의 트리를 집합과 같은 개념으로 보면 되고, 연결 관계가 없는 트리끼리 서로 분리 집합이라 보면 됩니다. 분리 집합은 합집합 말고는 연산이 따로 없기 때문에 구현은 쉽지만, 그래프 이론에서 많이 사용되므로 잘 알아 두고 넘어가야 합니다. 집합 생성 function Set(data) { this.data = data; this.parent = null; } const set1 = new Set(1); const set2 = new Set(2); 집합은 부모만 알면 되기 때문에, 트리..
수식 트리 (Expression Tree)
수식 트리 (Expression Tree)
2021.10.26Expression Tree 🙂 수식 트리(Expression Tree)는 이진 트리를 활용한 대표적인 케이스입니다. 수식 트리를 만들기 위해서는 몇 가지 조건을 충족해야 합니다. 하나의 연산자가 두 개의 피연산자를 취한다는 가정 하에 피연산자는 무조건 잎 노드여야 하며, 연산자는 가지 또는 루트 노드여야 합니다. 수식 트리는 후위 표현식을 사용하면 쉽게 만들 수 있는데, 후위 표현식을 뒤에서부터 분해하여 하나씩 노드로 만들어 연결하면 됩니다. 본문의 수식 트리는 하나의 연산자가 무조건 두 개의 피연산자를 취한다는 가정을 하고 구현했습니다. 노드 생성 function Node(data) { this.data = data; this.left = null; this.right = null; } 수식 트리는 ..
이진 트리 (Binary Tree)
이진 트리 (Binary Tree)
2021.10.26Binary Tree 🙂 이진 트리(Binary Tree)는 최대 2개의 자식을 가질 수 있는 노드들로 구성된 트리입니다. 데이터를 2개까지만 담을 수 있어 저장의 용도로 쓰기에는 조금 아쉬운 트리이지만, 데이터를 아주 빠르게 찾을 수 있는 이진 탐색(Binary Search)이나 수식을 트리 형태로 표현하여 계산하는 수식 트리(Expression Tree) 등에 활용할 수 있는 개성 넘치는 트리입니다. 이진 트리의 종류로 포화 이진 트리(FBT: Full Binary Tree)와 완전 이진 트리(CBT: Complete Binary Tree)라는 것도 있습니다. 포화 이진 트리는 잎이 되는 모든 노드가 채워진 이진 트리를 의미하고, 완전 이진 트리는 잎이 되는 노드들이 왼쪽부터 빼곡하게 자리를 채운 트..
LCRS 트리 (LCRS Tree)
LCRS 트리 (LCRS Tree)
2021.10.25LCRS Tree 🙂 LCRS 트리에서 LCRS는 Left Child, Right Siblings를 의미합니다. 그렇기에 이 트리는 왼쪽에는 자식이 붙고, 오른쪽에는 형제 노드만 붙는 형태의 트리라 볼 수 있습니다. 일반적으로 트리를 표현하는 방법은 다소 복잡한 편이지만, 이 트리는 왼쪽 자식에 대한 포인터와 오른쪽 형제에 대한 포인터만 있으면 모든 노드를 참조할 수 있기 때문에 구현이 간단합니다. 이 외에도 트리를 표현하는 방법으로 이진 트리(Binary Tree)가 있는데, 다음 시간에 알아 보도록 하겠습니다. 노드 생성 function LCRSNode(data) { this.data = data; this.leftChild = null; this.rightSibling = null; } const ..
큐 (Queue)
큐 (Queue)
2021.10.14Queue 🙂 큐(Queue)는 스택과 함께 대표적인 자료구조입니다. 스택이 Last In, First Out(LIFO)의 구조를 띄고 있었다면, 큐는 First In, Fist Out(FIFO)라는 선입선출 구조를 띄고 있습니다. 그리고 큐 역시 각 동작마다 명칭이 정해져 있는데, 큐의 마지막에 새로운 데이터를 추가하는 작업을 인큐(Enqueue), 그리고 맨 앞의 데이터를 빼는 작업을 디큐(Dequeue)라 합니다. 큐를 구현할 때는 디큐(Dequeue)가 일어날 때마다, 맨 앞을 가리키는 front의 값이 하나씩 뒤로 이동하는 것을 유의해야 합니다. 자바스크립트에서는 배열 프로토타입의 메소드 중 push와 shift로 큐를 간단하게 구현할 수 있지만, 본문의 코드에서는 사용하지 않았습니다. 큐 프로..
스택 (Stack)
스택 (Stack)
2021.10.14Stack 🙂 스택(Stack)은 맨 처음 들어간 것이 가장 마지막에 나오는 자료구조를 말합니다. 이러한 구조를 Last In, First Out(LIFO) 또는 First In, Last Out(FILO) 구조라 부릅니다. 스택은 다음에 다뤄 볼 큐(Queue)와 함께 소프트웨어 분야에서 정말 중요한 구조입니다. 프로그램들이 이용하는 자동 메모리 영역도 스택 구조로 되어 있고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다. 링크드 리스트를 만들 때는 노드를 추가하고 제거하는 과정에 별다른 이름이 없었지만, 스택과 큐는 명칭들이 정해져 있습니다. 데이터를 스택에 추가하는 작업을 push라 하며, 데이터를 제거하는 작업을 pop이라 합니다. 기본적으로 스택은 배열 또는 링크드 리스트를 이..
원형 링크드 리스트 (Circular Linked List)
원형 링크드 리스트 (Circular Linked List)
2021.10.13Circular Linked List 🙂 원형 링크드 리스트(Circular Linked List)는 처음 노드와 마지막 노드를 연결했다는 점에서 더블 링크드 리스트와 차이가 있습니다. 그렇기 때문에 마지막 노드를 제거할 때는 첫 노드의 이전 노드를 참조해서 제거하면 되므로 상대적으로 속도가 빠릅니다. 물론 이 경우에 한해서만 그렇고, 나머지는 다른 링크드 리스트들과 동일한 성능을 보입니다. 노드 & 리스트 생성 function Node(data) { this.data = data; this.prev = null; this.next = null; } function LinkedList() { this.head = null; this.length = 0; } 원형 링크드 리스트의 노드와 리스트는 더블 링크..
더블 링크드 리스트 (Doubly Linked List)
더블 링크드 리스트 (Doubly Linked List)
2021.10.13Doubly Linked List 🙂 더블 링크드 리스트(Doubly Linked List)는 기존의 링크드 리스트가 한 방향(Tail 방향)으로만 탐색 가능하던 것을 보완하기 위해 만들어진 자료구조입니다. 더블 링크드 리스트의 노드는 next 외에도 prev라는 것을 멤버 변수로 갖고 있는데, 이 변수의 값을 통해 바로 이전의 노드를 참조할 수 있습니다. 그렇다 해도 결국 리스트 내에 있는 head를 통해 하나씩 순차적으로 접근해야 하기 때문에, 단일 링크드 리스트와 특별하게 다른 부분은 없습니다. 노드 & 리스트 생성 class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } class Linked..