코딩/백준 (Python)
백준 11279번: 최대 힙 (Python)
접근 힙 트리(heap tree)란 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 힙에는 가장 큰 값을 구하기 위한 최대 힙과, 가장 작은 값을 구하기 위한 최소 힙이 있으며, 공통적으로 힙은 항상 완전 이진 트리(트리의 위부터 아래, 왼쪽에서 오른쪽 순서로 빠짐 없이 채워져 있는 트리)의 형태를 가지고 있어야 한다. 최대 힙은 부모의 값은 항상 자식들의 값보다 크거나 같아야 하고, 최소 힙은 부모의 값이 항상 자식보다 작거나 같아서, 이진 트리의 최대값, 혹은 최소 값을 구할 때 힙의 첫번째 요소를 통해 바로 구할 수 있게 된다. 이 문제에서는 최대 힙을 사용하여 문제를 풀며, 힙의 경우에는 python에 heapq 라이브러리가 있지만 원리를 제대로 다시 이해하기 ..
2021. 4. 5. 23:07
최근댓글