Tree
-
자료구조와 알고리즘, Tree, Priority QueueData Structure & Algorithm 2024. 6. 28. 18:21
우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지는 데이터 구조로, 일반적인 큐와 달리 요소들이 우선순위에 따라 제거됩니다. 우선순위 큐는 큐의 일종이지만, 요소를 삽입할 때 그 우선순위에 따라 적절한 위치에 배치하고, 제거할 때는 가장 높은(또는 낮은) 우선순위를 가진 요소를 먼저 제거합니다.우선순위 큐의 특징우선순위에 따른 요소 관리: 각 요소는 우선순위를 가지고 있으며, 큐의 요소는 우선순위에 따라 정렬됩니다.삽입 및 제거: 삽입 연산과 제거 연산은 모두 우선순위를 고려하여 수행됩니다.응용 분야: 작업 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등에서 자주 사용됩니다.구현 방법우선순위 큐는 다양한 방법으로 구현할 수 있지만, 가장 효율적인 방법은 힙(heap) 자료구조를..
-
자료구조와 알고리즘, Tree, Binary HeapData Structure & Algorithm 2024. 6. 28. 18:20
이진 힙(Binary Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 힙 속성을 만족하는 자료 구조입니다. 힙 속성은 다음과 같은 두 가지 형태로 구분됩니다:최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조.최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조.이진 힙의 특징완전 이진 트리: 이진 힙은 항상 완전 이진 트리입니다. 즉, 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 경우 왼쪽부터 차례대로 노드가 채워져 있습니다.힙 속성: 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같고, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.이진 힙의 구현이진 힙은 주로 배열을 ..
-
알고리즘, Tree, DFSData Structure & Algorithm 2024. 6. 27. 16:31
깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나로, 가능한 한 깊이 있는 노드를 우선으로 탐색합니다. DFS는 스택(stack) 자료 구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있습니다.DFS의 특징깊이 우선 탐색: 가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상 깊이 갈 수 없을 때 다음 인접한 노드로 이동합니다.스택 사용: DFS는 LIFO(Last In, First Out) 특성을 가진 스택을 사용하여 다음에 탐색할 노드를 관리합니다. 재귀적 구현에서는 함수 호출 스택을 사용합니다.경로 탐색: 그래프나 트리에서 경로를 탐색할 때 유용하며, 모든 경로를 탐색하는 문제에 적합합니다.DFS의 구현 (자바스크립트 예..
-
알고리즘, Tree, BFSData Structure & Algorithm 2024. 6. 27. 16:30
너비 우선 탐색(Breadth-First Search, BFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나입니다. BFS는 시작 노드에서 출발하여 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드들의 인접 노드를 탐색하는 방식으로 진행됩니다. 이는 주로 큐(queue) 자료 구조를 사용하여 구현됩니다.BFS의 특징레벨별 탐색: BFS는 트리 또는 그래프의 레벨을 기준으로 노드를 탐색합니다. 즉, 첫 번째 레벨(루트 노드)에서 시작하여 다음 레벨로 진행합니다.최단 경로 탐색: 무방향 그래프에서 BFS는 시작 노드에서 다른 노드로 가는 최단 경로를 찾을 수 있습니다.큐 사용: BFS는 FIFO(First In, First Out) 특성을 가진 큐를 사용하여 다음에 탐색할 노드를 관리합니다.BFS의..
-
자료구조와 알고리즘, Tree, Binary Search TreeData Structure & Algorithm 2024. 6. 26. 21:25
이진 탐색 트리(Binary Search Tree, BST)는 데이터의 효율적인 저장, 검색, 삽입 및 삭제를 위해 사용되는 트리 구조입니다. 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다. 이러한 특성 덕분에 이진 탐색 트리는 정렬된 데이터를 효율적으로 처리할 수 있습니다.이진 탐색 트리의 특성모든 노드의 값은 유일합니다.왼쪽 서브트리의 모든 노드 값은 부모 노드 값보다 작습니다.오른쪽 서브트리의 모든 노드 값은 부모 노드 값보다 큽니다.왼쪽 및 오른쪽 서브트리도 각각 이진 탐색 트리입니다.주요 연산삽입 (Insert): 새로운 값을 올바른 위치에 추가합니다.검색 (Search): 특정 값이 트리에 존..