본문 바로가기

🛠️Language/python3

[python] 힙(heap)과 힙큐(heapq)란? 힙(heap) 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 완전 이진트리 힙 property A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다. 최소 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 된다. 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 키 값의 대소 관계 부모/자식 노드 ⭕ 형제노드 ❌ 시간복잡도 O(log n) 최소힙(heapq 모듈을 사용하지 않고 구현) # 최소힙 # 힙 삽입 연산 def heap_push(item): heap.append(item) child = len(heap) -.. 2023. 8. 11.
[python] list 삭제 메서드 차이 + 요소 추가 list 원소 삭제 index로 제거 1️⃣ del a = [1, 2, 3, 4, 5, 6, 7] del a[1] print(a) # [1, 3, 4, 5, 6, 7] 2️⃣ pop : list.pop(인덱스) user_1 = ['수진', '민호', '나빈'] user_1.pop(1) # '민호' 삭제 print(user_1) # ['수진', '나빈'] 값으로 제거 1️⃣ remove : list.remove(삭제할 원소) a = [1, 2, 3, 4, 5, 6, 7] a.remove(3) print(a) # [1, 2, 4, 5, 6, 7] a.remove(9) # Traceback (most recent call last): # File "", line 1, in # ValueError: list.r.. 2023. 6. 30.
[python] 데크(deque)란? 데크(deque)의 개념 큐(queue) 선입선출(FIFO) 방식 데크(deque) 양방향 큐 앞, 뒤 양쪽 방향에서 element 추가 제거 가능 append와 pop이 압도적으로 빠름 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거의 경우, 일반적인 리스트(list)는 O(n) 소요, 데크(deque)는 O(1) 소요 사용법 from collections import deque deq = deque() # Add element to the start deq.appendleft(10) # Add element to the end deq.append(0) # Pop element from the start deq.popleft() # Pop element from .. 2023. 6. 29.

티스토리툴바