학습 주제
힙(Heap)의 심화 학습

학습 내용

이번엔 효율성 테스트도 들어가기에 효율성도 고려해야 함.

• 실행시간을 고려해야 함

제한 사항

• 모든 음식을 섞었지만 음식을 K 이상 못 만들경우 -1

문제의 해결 - 예제

가장 작은 두 음식을 정해진 방법으로 하나의 음식 5를 구함
새로운 음식 5를 다시 배열에 집어넣음

아직 모든 음식이 K 이상 스코빌이지 않으므로 이어서 진행

13은 배열 내 크기 고려하여 집어넣음


가장 작은 수 9는 요구하는 K 값보다 크므로, 그간 수행했던 횟수 2를 return

알고리즘의 복잡도

• 최악의 경우 수가 하나 남을 때까지 섞을 경우, 답이 나올수도 안나올 수도 있음.

• 정확히는 n^2 절반정도이지만, O(n^2)
  

힙 (Heaps)

• 성질: 한번에 상수시간 내에 가장 작은/큰 값으 찾을 수 있음
• 연산
  • 힙 구성 (heapify) O(NlogN)
  • 삽입 (insert) - O(logN)
  • 삭제 (remove) - O(logN)

힙의 구현

배열에 집어넣고 힙 구성 가능해 공간 효율성이 높음

힙의 응용

어려운 점

힙을 구성하는 연습을 해봤었는데, 바로 알고리즘이 떠오르지 않았음. 다시 복습해보자.