목록동빈북 (14)
소피it블로그
자료 출처: https://youtu.be/AjFlp951nz0 1. 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 단순히 리스트를 이용하여 구현하는 방식: 삽입시 O(1), 삭제시 O(N)의 시간복잡도 힙(heap) 자료구조를 이용하여 구현하는 방식: 삽입, 삭제시 각각 O(logN)의 시간복잡도 2. 힙 (Heap) 완전 이진 트리의 일종인 자료구조로, 항상 루트 노드를 먼저 제거한다. 최소 힙 (Min Heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터가 우선적으로 제거됨 따라서 최소 힙에 넣었다 빼면 오름차순으로 정렬됨(작은 데이터부터 제거되므로) 최대 힙 (Max Heap) 루트 노드가 가장 큰 값을 가짐 값이 큰 데이터가 우선적으로 제거됨 따라서 최대 힙에 ..
자료 출처: https://youtu.be/94RC-DsGMLo 1. 이진탐색이란? 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식으로 동작하는 알고리즘 시작점, 끝점, 중간점을 이용한다. 시간 복잡도: O(logN) 재귀 또는 반복문을 이용하여 구현할 수 있다. 이하는 재귀를 이용하여 푸는 법. # 재귀 방식으로 구현 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, ..