[1주차-5] 코딩테스트 연습 - 힙, DFS/BFS, 동적 계획법(Dynamic Programming)
힙(Heap) 힙 알고리즘을 이용하면 최대와 최소를 빠르게 찾을 수 있고 일반적으로 완절 이진 트리(배열로 구현 가능)로 구성된다. 문제에서 리스트 내의 원소를 모두 정렬하지 않고 최대나 최소만을 필요로 할 때, 효과적으로 사용될 수 있다. max heap: 최대의 원소를 빠르게 꺼내는 방법 min heap: 최소의 원소를 빠르게 꺼내는 방법 힙 연산: 힙 구성(NlogN), 삽입 O(logN), 삭제(logN) 힙의 응용: 정렬(heapsort), 우선 순위 큐 #파이썬에서 힙의 적용 import heapq L = [1,2,3,4,5] x = 7 heapq.heapify(L) #리스트 L로부터 min heap 구성 m = heapq.heappop(L) #min heap L에서 최소값 삭제(반환) hea..
2023. 4. 14.
