사전 지식 정리

힙 (Heap)

• 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조

  • 우선순위가 가장 높은 데이터를 가장 먼저 삭제

• 대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원

  → 일반적으로 코딩 테스트 환경에서 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현할 일은 없음

• 종류

  • 최소힙
    • 값이 낮은 데이터가 먼저 삭제
  • 최대힙
    • 값이 큰 데이터가 먼저 삭제

• 파이썬 라이브러리

  • PriorityQueue
  • heapq (권장)

  → 대부분 프로그래밍 언어에서 우선순위 큐 라이브러리에 데이터의 묶음을 삽입하면, 첫 번째 원소를 기준으로 우선순위를 설정

  → 기본적으로 파이썬은 최소힙 구조로 라이브러리가 구현

<aside> 💡 최소힙 ←→ 최대힙 변환 사용 팁

- 부호를 이용해 넣고, 빼고 나서 다시 - 적용

</aside>

최단 경로 (Shortest Path) 알고리즘

정의

• 가장 짧은 경로를 찾는 알고리즘
• ‘길찾기’ 알고리즘이라고도 불림