[알고리즘 고득점 kit] 힙 (개념, 문제풀이)

• 힙은 우선순위 큐를 위해 만들어진 자료구조

우선순위 큐

• 우선순위 큐란?
  • 큐 : FIFO 형식의 자료구조
  • 우선순위 큐는 큐에 우선순위라는 개념을 접목시킨 자료구조이다.
  • 따라서 우선순위 큐는 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조.

힙

• 힙이란?
  • 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조
  • 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
  • 반정렬 상태를 유지
  • 이진 탐색 트리와 달리 중복된 값이 허용된다.

힙의 종류

• 최대 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

힙의 데이터 저장 / 삭제 개념

• 최소 힙에 저장할 때
  • 들어올 새 노드를 우선 순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장
  • 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다
  • 올바르게 위치할 때까지 B 반복
• 최소 힙에서 삭제할 때
  • 우선순위 큐의 pop == 가장 우선순위가 높은 데이터를 빼낸다.
    1. 루트 노드를 반환하고 마지막 노드를 루트 노드 자리에 옮긴다.
    2. n의 왼쪽, 오른쪽 자식노드 중 더 우선순위가 높은 것과 비료를 진행한다.
    3. 최소 힙의 구조를 유지할 때까지 B 반복
    ⇒ 이렇게 힙의 구조를 유지하는 과정을 heapify라고 한다.

파이썬의 우선순위 큐

• heapq 모듈

import heapq
# 파이썬의 heapq 모듈은 최소 힙을 기본으로 구현되어 있다.

pq = []

heapq.heappush(pq, (1, '작업1')) # (우선순위, 값)
heapq.heappush(pq, (4, '작업4'))
heapq.heappush(pq, (3, '작업3'))
heapq.heappush(pq, (2, '작업2'))

print(heapq.heappop(pq)) 
print(heapq.heappop(pq))

• PriorityQueue 클래스

from queue import PriorityQueue

pq = PriorityQueue()

pq.put((1, '작업1'))
pq.put((3, '작업3'))
pq.put((2, '작업2'))

print(pq.get())
print(pq.get())

⇒ PriorityQueue는 스레드 안전을 제공하므로 멀티스레딩 환경에서 유용하지만, 단일 스레드 환경에서는 heapq가 더 간편하다.

문제 풀이

JS로도 풀어보고 싶었지만 JS에는 heap 모듈이 따로 없고 코테 외에서는 라이브러리를 사용할 수 있다.

 

더 맵게

---

• 파이썬 풀이

• # 스코빌 섞을 수 없는 경우: 길이가 2보다 짧을 시 -1
  
  import heapq
  
  def solution(scoville, K):  
      heapq.heapify(scoville)
      
      mix_count = 0
      
      while scoville[0] < K:
          if len(scoville) < 2:
              return -1
          
          first = heapq.heappop(scoville)
          second = heapq.heappop(scoville)
          new_food = (first + second * 2)
          heapq.heappush(scoville, new_food)
          mix_count += 1
              
      return mix_count
  ​

• 자바스크립트 풀이⇒ 이 코드는 모든 테스트 케이스를 통과하지만 효율성에서 걸린 코드이다.

• function solution(scoville, K) {
      scoville.sort((a, b) => b - a);
      let mix_count = 0;
      while (scoville.at(-1) < K) {
          if (scoville.length < 2) return -1;
          
          let first = scoville.pop();
          let second = scoville.pop();
          let new_food = first + second * 2;
          
          scoville.push(new_food);
          scoville.sort((a, b) => b - a);
          
          mix_count++;
      }
      return mix_count;
  }
  

 

디스크 컨트롤러

---

• 파이썬 풀이

이중우선순위큐

---

• 파이썬 풀이