코테볼 때 자주 사용하는 라이브러리 그 두 번째로 소개시켜드릴 라이브러리는 heapq 입니다. 단순한 sorting 문제임에도 불구하고 효율성에서 항상 터져버리는 경우가 종종 있는데, 그럴 때 heapq를 사용해서 똑같은 알고리즘으로 구현하면 통과하는 경우가 있습니다.
그만큼 빠른 heapq에 대해 알아보도록 하죠.
heap 자료구조
먼저 heap 이라고 하는 자료구조에 대해 알면 편합니다. 기능에만 집중해도 되지만 일단 어떤 걸 기준으로 내놓는지를 알아야 어디에 써먹을지를 떠올릴 수 있겠죠?
heap은 다음의 규칙을 만족하는 이진트리(Binary Tree) 구조를 말합니다.
힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리입니다. 이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다.
출처 : https://docs.python.org/ko/3/library/heapq.html
쉽게 말해 아래와 같은 그림을 가진 구조를 말합니다.
가만 보면 어떤 node든 그 자식 노드보다 항상 작은 값을 가지고 있죠!
위의 그림의 어느 수를 보시든 그 아래에 2개의 수보다 항상 작은 값을 가지는 것을 확인하실 수 있습니다.
heapq는 특히 최소 heap을 나타낸 라이브러리인데요, list 내의 최솟값이나 최댓값을 구할 때 매우 유용하게(빠르게) 사용됩니다.
아래와 같은 List가 있다고 해봅시다.
lst = [10,9,8,7,1]위의 list에서 정렬 후 가장 작은 값을 따로 빼내야하는 작업을 해야한다고 해봅시다. 가장 쉬운 방법은 min()함수를 사용하거나 sort 해서 index[0] 을 해서 찾는 방식이겠죠?
원소가 얼마 안 될 때는 python의 sort 알고리즘이 쉽고 적당하지만 원소의 수가 아~주 많을 때는 얘기가 다릅니다.
원소의 수가 아주 많을 때 효율적으로 최대, 최소값을 찾을 수 있게 해주는 것. 그것이 바로 heap 입니다.
import heapq
heap 자료구조를 사용하기 위해 python에서 기본적으로 제공하는 heapq 라이브러리를 사용합니다.
heap을 사용하기 전에, 기본적으로 list가 주어졌을 때 위의 사진처럼 heap 자료구조로 바꾸는 작업부터 진행을 해야겠죠? 아래의 코드로 가능합니다.
heapq.heapify()
import heapq
lst = [10,9,8,7,1]
heapq.heapify(lst)
print('힙 자료구조로 바뀐 List\n',lst,'\n')Output
힙 자료구조로 바뀐 List
[1, 7, 8, 10, 9]
단순히 list sort 처럼 작은 수부터 나오는 게 아니라 위의 그림과 같은 순서대로 나와있는 것을 확인하실 수 있습니다.
heapq.heappop()
heap에서 가장 작은 값을 뽑아낼 때 사용하는 함수입니다.
print('heappop으로 뽑은 가장 작은 값\n', heapq.heappop(lst))
print('heappop하고 난 다음의 heap\n', lst)Output
heappop으로 뽑은 가장 작은 값
1
heappop하고 난 다음의 heap
[7, 9, 8, 10]
기본적으로 python list의 pop()과 크게 다를 건 없습니다. 다만 가져오는 값이 항상 최솟값이라는 차이가 존재하죠.
heapq.heappush()
heappop()이 가장 작은 값을 뽑아오는 것이었다면 heappush()는 원소를 heap 자료 형식에 맞게 추가하는 함수입니다.
heapq.heappush(lst,3)
heapq.heappush(lst,4)
print('heappush로 원소를 넣은 다음의 heap\n',lst)Output
heappush로 원소를 넣은 다음의 heap
[3, 7, 4, 10, 9, 8]
list.append()와 다른 것은, append 함수는 list의 가장 뒤에 무조건 추가하게되지만 heapq의 heappush()는 3과 4를 넣었음에도 불구하고 순서대로 들어가는 것이 아니라 heap 자료에 맞게 들어간 것을 확인하실 수 있습니다.
heap 문제
여기까지 푸셨으면 아래의 문제를 푸실 수 있습니다.
프로그래머스 Lv2에 해당되는 문제입니다.일반적인 sort로 풀면 효율성 테스트에서 시간초과가 되기 때문에 heap을 이용합니다.
한번 풀어보시는 것도 좋을 것같네요!
