힙(Heap) 고득점 kit 풀이 완료, 후기

힙으로 우선순위 큐를 구현한다면, 삽입과 삭제가 모두 O(logn)으로 이루어진다.

시간복잡도 계산 시 logn은 거의 상수로 봐도 무방할 정도다. 완전히 상수는 아니지만 n과 비교해도 엄청난 차이임을 알 수 있다. 

삽입, 삭제가 원활하게 이루어져야 하는 프로그램에서는 힙구조 우선순위 큐를 이용하면 매우 좋다.

C++에서 priority_queue 라이브러리를 사용하는 방법에 대해 포스팅해둔 글이 있으니 참고하면 좋을 것이다.

구조체의 특정 요소(변수)를 기준으로 우선순위를 정하는 방법도 같이 설명해두었다.

kimcoder.tistory.com/110?category=887628

삽입, 삭제 모두 O(logn)!! STL priority_queue 소개

고득점 kit의 Heap문제들중 디스크 컨트롤러가 꽤 난이도 있었던 것 같다.

디스크에 들어온 시각, 작업 시간 두 가지 정보를 동시에 이용해야 하는 문제라 소스 코드도 다소 복잡했다.

특히 이 문제를 해결한 후, 크게 자신감을 얻었다. 

 

문제모음

[난이도 중] 이중우선순위큐 kimcoder.tistory.com/102?category=888029

[난이도 중하] 더 맵게 kimcoder.tistory.com/142?category=888029

[난이도 중상] 디스크 컨트롤러 kimcoder.tistory.com/145?category=888029