자료구조2 [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 사용 용도 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 특징 힙(heap)을 이용한 구현 방법 루트 노드엔 우선순위가 높은 값이 들어간다. 힙에서는 항상 루트 노드를 제거한다. 힙은 완전 이진 트리 형태로 구성되어있다. import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) heap = [] for i in range(n, 0, -1): heappush(heap, i) print('-' * 15, 'heappop', '-' * 15) for i in ra.. 2023. 5. 10. [자료 구조] 자료 구조 시간 복잡도 자료 구조(data structure) 효율적으로 데이터를 관리하고, 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 자료구조 평균 시간 복잡도 자료 구조 접근 탐색 삽입 삭제 배열 (array) O(1) O(n) O(n) O(n) 스택 (stack) O(n) O(n) O(1) O(1) 큐 (queue) O(n) O(n) O(1) O(1) 이중 연결 리스트 (doublylinked list) O(n) O(n) O(1) O(1) 해시 테이블 (hash table) O(1) O(1) O(1) O(1) 이진 탐색 트리 (BST) O(log n) O(log n) O(log n) O(log n) AVL 트리 O(log n) O(log n) O(log n) O(log n) 레드 블랙 트리 O(log n) O(lo.. 2023. 3. 19. 이전 1 다음