자료구조

[자료구조] 힙

힙 힙(heap) 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조중 하나다! 우선순위 큐는 우선순위에 따라 처리하고 싶을 때 사용 예를들어 여러개의 데이터 중 자료구조에 넣었다가 우선적으로 꺼내고 싶은 데이터부터 꺼내서 체크할 때 우선순위 큐를 사용하면 효과적이다. PriorityQueue heapq 파이썬에서는 위 라이브러리로 구현할 수 있다. 최소힙, 최대힙을 이용하는데 최소힙을 사용할 경우 가장 낮은 데이터가 우선적으로 삭제되고 최대힙을 사용할 땐 가장 높은 데이터가 우선적으로 삭제됨 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선으로 방문하므로 최소힙을 사용하는 것이 적합! 우선순위 큐 구현 방식 삽입시간 삭제시간 리스트 O(1) O(N) 힙 O(logN) O(logN) ※해..

스택과 큐

자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입 : 데이터를 삽입 (PUSH) 삭제 : 데이터를 삭제 (POP) 스택 스택(stack)은 이름 그대로 쌓는걸 생각하면 된다. 블럭을 쌓는 놀이를 한다고 생각해보자 처음엔 차근차근 블럭을 아래에서 위로 쌓을 것이다. 다시 쌓은 블럭을 해체시키려면 위에서부터 하나씩 꺼내야한다. 즉 맨 마지막에 쌓은 블럭을 젤 먼저 뽑는 거다. 이를 선입후출이라고 한다! stack=[] stack.append(2) stack.append(3) stack.append(1) #stack->[2,3,1] stack.pop() #stack->[2,3] stack.pop() #stack->[2] stack.pop() #stack->[] 큐 큐(Queue)는 음식점 대기줄..