heapq1 [ Python ] Heap Programmers 문제를 풀면서 계속 시간 초과가 나는 이슈가 발생했습니다. sort() 로 인한 시간 초과임을 짐작해보았고, 이를 heap으로 해결할 수 있음을 확인했습니다. [ Heap ] python 에서는 heap을 heapq라는 함수를 제공해주고 있습니다. heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공합니다. 쉽게 설명하면 데이터를 추가하거나 삭제할 때, 가장 작은 값이 정렬되어 있는 자료구조입니다. 즉 데이터를 삽입하고 꺼낼 때, 전체를 다시 정렬해 줄 필요 없이 자료구조 알고리즘을 통해 결정됩니다. heap 구조는 pop, push 의 시간 복잡도가 굉장히 적습니다. heapq를 사용하지 않으면, sort() 를 사용해야 하고 이는 시간 초과를 발생시킬 수 있습니다. impo.. 2022. 6. 9. 이전 1 다음