Data Structure
-
[Data Structure] BST (Binary Search Tree)Data Structure 2024. 5. 24. 23:38
BST (Binary Search Tree)에 대해 정리하였습니다.Binary Search Tree 즉 이진탐색트리는 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리입니다. Binary Search Tree (BST)에서 값이 같은 노드, 즉 중복된 값을 처리하는 방법은 다양합니다. 1. 중복 값을 허용하지 않기2. 중복 값을 왼쪽 서브트리에 삽입3. 중복 값을 오른쪽 서브트리에 삽입4. 중복된 값의 카운트를 증가시키기 [ 장점 ]탑색 속도가 빠릅니다: 이진 탐색 트리는 데이터가 정렬된 상태를 유지하므로 탐색 속도가 빠릅니다. 이진 탐색 트리에서 데이터를 찾는 데 필요한 평균 시간 복잡도는 O(log n)입니다.간단한 구현: 이진 탐색 트리의 구현은..
-
[Data Structure] 힙(Heap)Data Structure 2024. 5. 19. 01:29
힙(Heap) 자료구조에 대해 정리하였습니다.힙(Heap) 자료구조는 트리 기반의 완전 이진 트리로, 특정한 순서 속성을 유지하는 데이터 구조입니다. 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분됩니다.일반적으로 배열을 통해 구현합니다. 최대 힙 (Max Heap):각 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.트리의 루트(root) 노드는 항상 최대값을 가집니다. 최소 힙 (Min Heap):각 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.트리의 루트 노드는 항상 최소값을 가집니다. [ 힙의 배열 표현 ]: 힙은 배열로 쉽게 표현할 수 있습니다. 배열 인덱스를 이용하여 부모와 자식 노드 간의 관계를 정의할 수 있습니다:부모 노드 인덱스: i왼쪽 자식 노드 인덱스: ..
-
[Data Structure] 링크드리스트Data Structure 2024. 5. 18. 01:27
링크드리스트(linked_list) 자료구조에 대해 정리하였습니다. [ 단일 링크드 리스트 (Singly Linked List) ] 각 노드는 데이터와 다음 노드를 가리키는 하나의 포인터를 포함합니다.마지막 노드의 포인터는 null을 가리키며 리스트의 끝을 나타냅니다.Node1 -> Node2 -> Node3 -> null [ 이중 링크드 리스트 (Doubly Linked List) ] 각 노드는 데이터를 포함하며, 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 가지고 있습니다.양방향 탐색이 가능하다는 장점이 있습니다.null Node2 Node3 -> null [ 원형 링크드 리스트 (Circular Linked List) ] 마지막 노드가 첫 번째 노드를 가리키도록 연결되어 있습..
-
[Data Structure] 큐(Queue) & 스택(Stack)Data Structure 2024. 5. 16. 23:59
큐(Queue)와 스택(Stack)자료구조에 대해 정리하였습니다.기본적인 자료구조 중 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말합니다. 일반 큐 (Linear Queue), 원형 큐 (Circular Queue), 우선순위 큐 (Priority Queue), 블로킹 큐 (Blocking Queue), 동기화 큐 (Synchronized Queue) 등 다양한 큐의 종류가 있습니다. Ex)- 프린터 대기열- 프로세스 관리- 운영 체제의 작업 스케줄링 class Queue { constructor() { this.items = []; } // 큐에 요소 추가 enqueue(element) { this.items..