[TIL] 알고리즘 TIL Day 2

아래 프로그래머스 문제를 for, while문을 이용해서 그냥 풀었는데 계속 효율성 0점이 나와서 이유가 뭔가 하고 찾아보았다. 자료구조를 공부하지 않아서 몰랐는데 이 문제에서 힙(Heap)을 쓰면 효율성이 확 올라간다! 그래서 오늘 TIL에서는 힙에 대해 간단히 정리하려고 한다.

🟡 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

Solution

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        min_sc = heapq.heappop(scoville)
        if min_sc >= K:
            return answer
        else:
            min_sc2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min_sc + min_sc2*2)
            answer += 1
    
    if scoville[0] >= K:
        return answer
    else:
        return -1

힙(Heap)

힙(Heap) 은 완전 이진트리의 일종으로 최댓값과 최솟값을 빠르게 찾기 위해 사용되는 자료구조이다.

1. 특징

• 최대 힙(Max Heap): 부모 노드의 key 값이 자식 노드의 key 값보다 크거나 같음
• 최소 힙(Min Heap): 부모 노드의 key 값이 자식 노드의 key 값보다 작거나 같음
• 항상 정렬된 상태를 유지
• key 값의 대소관계는 부모-자식 노드 사이에서만 존재하며, 형제노드 간에는 대소관계가 존재하지 않음
• 시간복잡도: $Olog(n)$

2. Python의 Heap module

• Module import

   import heapq
  

• 기존의 리스트를 힙으로 변환

   heapq.heapify(list)
  

• 노드 추가

   heapq.heappush(heap, node)
  

• 노드 제거

   heapq.heappop(heap)