heap (4) 썸네일형 리스트형 힙 (Heap) (3) 힙에 데이터 삭제 구현 (Max Heap 예) 힙 클래스 구현 4 - delete 1 보통 삭제는 최상단 노드 (root node)를 삭제하는 것이 일반적이다. 왜냐하면 힙의 용도는 최대값 또는 최소값을 root node에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이기 때문이다. class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) def pop(self): if len(self.heap_array) = len(self.heap_array):# array의 길이는 항상 전체 length에서 1을 더하게 되어 있다. len(ar.. 힙 (Heap) (2) 4. 힙 구현 힙과 배열 일반적으로 힙 구현 시 배열 자료구조를 활용한다. 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root node 인덱스 번호를 1로 지정하면, 구현이 조금 더 수월하다. 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1 위 그림을 보면, 가령 10 노드의 인덱스 번호가 2인데.. 힙 (Heap) 1. 힙 (Heap) 이란? 힙(Heap)이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 힙을 사용하는 이유는 다음과 같다. 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸리는 반면, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log n)이 걸린다. 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다. 즉, 최대값과 최소값을 찾는 기능이 필요할 때, 힙(Heap) 자료구조를 사용하면 매우 효율성을 높일 수 있는 것이다. 힙이란 자료구조는 트리를 기반으로 하는 변형된 형태의 정책을.. 다익스트라(Dijkstra) 최단 경로 알고리즘 가장 빠르게 도달하는 방법 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 조금 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩 테스트에서는 최.. 이전 1 다음
