본문 바로가기
반응형
SMALL

algorithm/자료구조14

레드-블랙 트리(Red-Black Tree) 레드-블랙 트리(Red-Black Tree)는 이진 탐색 트리의 한 종류로, 균형을 유지하기 위해 특정 규칙을 따르는 자료구조입니다. 이는 삽입, 삭제, 탐색과 같은 기본적인 동작들을 O(log n)의 시간 복잡도로 수행할 수 있게 해 줍니다. 레드-블랙 트리는 다음과 같은 성질을 만족합니다: 각 노드는 레드 혹은 블랙입니다. 루트 노드는 블랙입니다. 모든 리프 노드(NIL 노드)는 블랙입니다. 레드 노드의 자식 노드들은 모두 블랙입니다. (레드 노드는 연속되지 않습니다.) 각 노드로부터 해당 노드의 후손 리프 노드로 이어지는 모든 경로에는 같은 수의 블랙 노드가 존재합니다. 자바스크립트로 레드-블랙 트리를 구현하기 위해서는 먼저 노드를 정의하는 클래스와 트리를 정의하는 클래스가 필요합니다. 여기서는 간.. 2024. 3. 24.
해시테이블(Hashtable) 해시테이블(Hashtable)은 키(Key)를 값(Value)에 매핑하여 데이터를 저장하는 자료 구조입니다. 이를 통해 데이터의 추가, 검색, 삭제 등을 평균적으로 상수 시간(O(1))에 수행할 수 있습니다. 해시테이블의 핵심은 해시 함수(Hash Function)입니다. 해시 함수는 임의 크기의 데이터를 고정된 크기의 유일한 값(해시 코드)으로 변환합니다. 이 해시 코드는 배열의 인덱스로 사용되어, 데이터의 위치를 결정합니다. 해시 충돌(Hash Collision) 두 개 이상의 키가 같은 해시 값을 가지게 되는 경우를 해시 충돌이라고 합니다. 해시테이블 구현 시 충돌을 해결하는 방법은 여러 가지가 있지만, 가장 일반적인 두 가지 방법은 체이닝(Chaining)과 오픈 어드레싱(Open Addressi.. 2024. 3. 20.
그래프 그래프는 노드(정점)들과 그 노드들을 연결하는 간선(엣지)들의 집합으로 구성된 자료 구조입니다. 그래프는 네트워크 모델링, 경로 찾기, 소셜 네트워크 분석 등 다양한 분야에서 활용됩니다. 그래프는 크게 두 가지로 분류됩니다: 무방향 그래프(Undirected Graph): 간선에 방향이 없어, 두 정점이 서로 연결되어 있는 구조입니다. 방향 그래프(Directed Graph): 간선에 방향이 있어, 한 정점에서 다른 정점으로의 일방향 연결을 나타냅니다. 그래프는 또한 가중치가 있는 그래프와 가중치가 없는 그래프로 나눌 수 있으며, 가중치가 있는 그래프에서는 각 간선에 비용 또는 가중치가 할당됩니다. JavaScript에서 그래프 구현하기 JavaScript로 그래프를 구현할 수 있는 여러 방법이 있습니다.. 2024. 3. 20.
우선순위 큐(Priority Queue)와 덱(Deque) 우선순위 큐(Priority Queue)와 덱(Deque, Double-Ended Queue)은 모두 추상 자료형(Abstract Data Type, ADT)으로, 데이터를 저장하고 접근하는 데 사용되는 컬렉션입니다. 그러나 그들이 데이터를 관리하고 접근하는 방식에는 중요한 차이가 있습니다. 우선순위 큐(Priority Queue) 우선순위 큐는 각 요소가 우선순위와 함께 저장되는 자료구조입니다. 요소들은 우선순위에 따라 정렬되며, 요소를 제거할 때는 가장 높은 우선순위를 가진 요소가 먼저 제거됩니다. 우선순위 큐는 힙(Heap) 자료구조를 사용하여 효율적으로 구현될 수 있습니다. 힙을 사용하는 경우, 요소의 추가와 제거(특히, 최소값 또는 최대값의 제거)가 O(logN) 시간 복잡도를 가집니다. 사용 .. 2024. 3. 20.
이진힙(Binary Heap) 이진 힙(Binary Heap)은 완전 이진 트리를 기반으로 하는 자료 구조로, 주로 우선순위 큐를 구현하는 데 사용됩니다. 이진 힙은 크게 두 종류로 나뉩니다: 최소 힙(Min Heap)과 최대 힙(Max Heap)입니다. 최소 힙에서는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같아야 하며, 최대 힙에서는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같아야 합니다. 이로 인해 이진 힙의 루트 노드는 전체 트리에서 최소값(최소 힙의 경우) 또는 최대값(최대 힙의 경우)을 가지게 됩니다. 이진 힙을 자바스크립트로 구현하는 것은 배열을 사용하여 비교적 간단합니다. 힙 내의 각 요소들은 일련의 연산을 통해 관리되며, 주로 다음 네 가지 주요 연산을 구현합니다: 삽입(Insert):.. 2024. 3. 20.
DFS, BFS, 트리 순회(traversal) 이진트리에서 데이터를 검색하거나 방문하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 그리고 트리 순회(Traversal)가 있습니다. 각각의 방법은 특정 목적에 따라 사용되며, 이진트리의 모든 노드를 효율적으로 방문하는 다양한 전략을 제공합니다. 깊이 우선 탐색 (Depth-First Search, DFS) DFS는 트리의 깊이를 우선적으로 탐색하는 알고리즘입니다. 트리의 루트에서 시작하여 가능한 한 깊게 트리를 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 분기점으로 되돌아가 다른 경로를 탐색합니다. 이진트리에서 DFS를 구현하는 세 가지 주요 방법은 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)입니다. 전위 순회 (Preorder): .. 2024. 2. 25.
remove : 이진탐색트리(Binary Search Tree, BST) 이진탐색트리(Binary Search Tree, BST)에서 remove 메소드를 구현하는 것은 조금 더 복잡합니다. 노드를 제거할 때는 세 가지 주요 상황을 고려해야 합니다: 리프 노드 제거: 제거하려는 노드가 리프 노드인 경우, 단순히 그 노드를 제거하면 됩니다. 한 개의 자식을 가진 노드 제거: 제거하려는 노드가 하나의 자식만 가지고 있는 경우, 그 노드를 제거하고, 그 자식을 제거된 노드의 부모 노드에 연결합니다. 두 개의 자식을 가진 노드 제거: 제거하려는 노드가 두 개의 자식을 가지고 있는 경우, 노드의 오른쪽 서브트리에서 가장 작은 값을 찾거나(또는 왼쪽 서브트리에서 가장 큰 값을 찾아) 그 값을 제거하려는 노드의 위치로 이동하고, 원래 그 값을 가지고 있던 노드를 제거합니다. 아래는 BST.. 2024. 2. 25.
search : 이진탐색트리(Binary Search Tree, BST) 이진탐색트리(Binary Search Tree, BST)에서 search 메소드를 구현하는 것은 insert 메소드와 유사한 방식으로 진행할 수 있습니다. search 메소드는 트리 내에서 특정 데이터를 찾아 그 데이터가 존재하는지 여부를 반환하거나, 해당 데이터를 포함하는 노드를 반환합니다. 이 메소드 역시 재귀적인 방법을 사용하여 구현할 수 있습니다. 아래는 BST 클래스에 search 메소드를 추가한 예시입니다. 이 메소드는 주어진 데이터와 일치하는 노드를 찾으면 그 노드를 반환하고, 데이터를 찾지 못하면 **null**을 반환합니다. class Node { constructor(data, left = null, right = null) { this.data = data; this.left = le.. 2024. 2. 25.
insert : 이진탐색트리(Binary Search Tree, BST) 이진탐색트리(Binary Search Tree, BST)의 insert 함수를 구현하는 것은 자료구조의 기본을 이해하는 좋은 방법입니다. 이진탐색트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큰 특성을 가지고 있습니다. 이러한 성질을 이용하여 데이터를 정렬된 상태로 저장할 수 있으며, 검색, 삽입, 삭제 작업을 효율적으로 수행할 수 있습니다. 아래는 자바스크립트로 이진탐색트리를 구현하고, insert 메소드를 추가하는 간단한 예제입니다. class Node { constructor(data, left = null, right = null) { this.data = data; this.left = left.. 2024. 2. 25.
이진트리(Binary tree) 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다. 일반적으로 이진 트리는 검색, 정렬, 데이터 저장 등 다양한 컴퓨터 과학 문제를 해결하는 데 사용됩니다. 이진 트리의 다양한 종류 중에 "Full Binary Tree", "Perfect Binary Tree", "Complete Binary Tree", "Degenerate (or Pathological) Binary Tree", "Balanced Binary Tree" 들은 각각 고유한 특성을 가지고 있지만, 몇 가지 공통적인 유사점도 공유합니다. 여기서는 이 다섯 가지 이진 트리 유형의 주요 특징과 함께 그들이 공유하는 유사점에 대해 설명합니다. 주요 특징 Full Binary Tree: 모든 노드가 0개 또는 2개의.. 2024. 2. 24.
스택(Stack), 큐(Queue), 트리(Tree) 스택(Stack) 스택은 후입선출(LIFO, Last-In-First-Out) 방식의 자료 구조입니다. 가장 마지막에 추가된 요소가 가장 먼저 제거됩니다. 자바스크립트에서 스택은 배열을 통해 쉽게 구현할 수 있습니다. 배열의 push 메서드로 요소를 스택에 추가하고, pop 메서드로 가장 마지막에 추가된 요소를 제거할 수 있습니다. let stack = []; stack.push(1); // 스택에 1 추가 stack.push(2); // 스택에 2 추가 console.log(stack.pop()); // 가장 마지막에 추가된 2를 제거하고 출력 console.log(stack); // 남아 있는 스택의 요소 확인 큐(Queue) 큐는 선입선출(FIFO, First-In-First-Out) 방식의 자료 .. 2024. 2. 22.
연결 리스트에서 노드(Node)란? 연결 리스트에서 노드(Node)는 리스트의 기본 단위로, 데이터와 다음 노드에 대한 참조(포인터)를 포함하는 객체나 구조체입니다. 연결 리스트는 이러한 노드들이 서로 연결되어 있는 구조로, 각 노드는 다음 노드를 가리키는 방식으로 연결됩니다. 연결 리스트의 각 요소를 노드라고 부르며, 각 노드는 최소 두 부분으로 구성됩니다: 데이터(Data): 노드가 저장하고 있는 실제 값이나 정보입니다. 이 데이터는 정수, 문자열, 또는 복잡한 객체와 같은 어떤 타입도 될 수 있습니다. 참조(Next Pointer): 다음 노드를 가리키는 포인터나 참조입니다. 이를 통해 연결 리스트의 다음 요소와 연결됩니다. 마지막 노드의 경우, 이 포인터는 일반적으로 null이나 리스트의 끝을 나타내는 특별한 값을 가집니다. 연결 .. 2024. 2. 16.
연결리스트의 시간복잡도 class LinkedList { length = 0; head = null; add(value) { if (this.head) { //head에 값이 있을때 let current = this.head; while (current.next) { //다음이 없을때까지 계속 반복(다음이 없다는건 값이 비어있다는 것) current = current.next; } current.next = new Node(value); //current.next가 없을때 넣어준다 } else { //head에 값이 없을때 this.head = new Node(value); //그냥 해당 값을 추가하면된다 } this.length++; //값이 들어갔으니깐 길이가 하나 길어진다 return this.length; //lengt.. 2024. 2. 9.
연결 리스트(Linked List) 연결 리스트(Linked List)는 데이터 항목들이 노드(Node)라는 요소에 저장되며, 각 노드가 다음 노드를 가리키는 포인터(Pointer) 또는 참조(Reference)를 통해 서로 연결되어 있는 선형 데이터 구조입니다. 연결 리스트는 배열과 비교했을 때, 동적 크기 조정이 용이하고, 삽입과 삭제 연산이 더 효율적일 수 있습니다. 다만, 임의 접근(Random Access)이 불가능하여 특정 인덱스의 요소에 접근하기 위해서는 처음부터 해당 요소까지 순회해야 합니다. 연결 리스트에는 주로 다음과 같은 종류가 있습니다: 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 포인터를 가지고 있습니다. 따라서 리스트를 한 방향으로만 순회할 수 있습니다. 이중 연결 리스.. 2024. 2. 9.
728x90
반응형
LIST

티스토리툴바