Computer Science32 [자료구조] 힙(Heap) 목차 힙(Heap) 우선순위 큐(Priority Queue) 힙을 보기전에 먼저 우선순위 큐를 살펴보도록 하겠습니다. 우선순위 큐는 각각의 원소가 우선순위를 가지고 있으며, 우선순위가 높은 순서대로 원소를 제거할 수 있는 추상 데이터 타입( Abstract Data Type, ADT )입니다. 추상 데이터 타입(Abstract Data Type, ADT)은 데이터와 그 데이터에 대한 연산들을 추상적으로 정의한 것입니다 ADT는 데이터의 타입과 그 타입에 대해 수행할 수 있는 연산들의 집합으로 구성되지만, 이러한 연산들의 구현 방법은 정의하지 않는 것입니다. ADT 예시 스택(Stack) ADT는 데이터의 삽입(push), 삭제(pop), 조회(peek) 등의 연산을 정의하지만, 이러한 연산들이 배열을 사.. 2024. 4. 20. [자료구조] 이진 탐색 트리(BST:Binary Search Tree) 목차 이진 탐색 트리(BST:Binary Search Tree) 개념 이진 탐색 트리의 각 노드의 값은 왼쪽 서브트리에 있는 값들보다 커야 하고, 오른쪽 서브트리에 있는 값들보다는 작아야 합니다. 삽입 def insert(self, data): if self.root is None: self.root = Node(data) else: self._insert(self.root, data) def _insert(self, parent_node, data): if data < parent_node.data: if parent_node.left is None: parent_node.left = Node(data) else: self._insert(parent_node.left, data) else: if par.. 2024. 4. 20. [자료구조] 버킷 정렬(Bucket Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 버킷 정렬(Bucket Sort) 개념 버킷 정렬은 주어진 배열을 범위를 나눠서 여러 개의 버킷(빈)으로 나누어 담은 뒤 각각의 버킷을 정렬하는 방식입니다. 각각의 버킷에 기존의 정렬 알고리즘을 적용하여 정렬을 진행합니다. 따라서 Non-comparison 기반 정렬이면서, comparison 기반 정렬이 됩니다. 버킷 정렬은 데이터가 균등하게 분포.. 2024. 4. 17. [자료구조] 기수 정렬(Radix Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 기수 정렬(Radix Sort) 개념 Radix Sort는 기존 Counting Sort(계수 정렬) 방식에서의 단점을 보완하기 위해 나온 방법입니다. Counting Sort의 경우 K(최댓값과 최솟값의 차이)가 커지게 되면 메모리를 많이 차지하게 되어 작업 속도가 느려질 수 있어 Counting Sort의 장점이 사라지게 됩니다. 또한 Count.. 2024. 4. 17. 이전 1 2 3 4 ··· 8 다음
