Daniel's blog

integer로 구성된 sticks라는 input array의 모든 요소를 이어 붙이는 문제다. 이 때 더할 때 마다 발생하는 합이 최소가 되도록 하는 문제다. sorting을 통해 풀이를 해야하나 잠시 생각했지만 Min heap을 사용하면 쉽게 구현이 가능하다. class Solution: def connectSticks(self, sticks: List[int]) -> int: mh = sticks ret = 0 heapify(mh) while len(mh) > 1: m1 = heappop(mh) m2 = heappop(mh) sum_ = m1 + m2 ret += sum_ heappush(mh, sum_) return ret

Heapify :Heapify is the process of creating a heap data structure from a binary tree represented using an array. : Heapify란 배열(Array)로 표현된 이진 트리(Binary tree)의 자료구조를 갖는 힙(Heap)을 생성하는 과정이다. 알고리즘 과제로 Heap을 Build하는 문제에 대해 알고리즘을 제시해야했고, 목표 시간복잡도(Time-Complexity)는 Linear time(O(n))이었다. Heap을 접할 때 기본적으로 함께 알게 되는 함수 중 하나가 Insert() 함수다. Insert() 함수의 시간복잡도는 Tree의 Height(높이)만큼 비교가 필요해 O(log n)이다. 이를 n개의 노드..