반응형 Algorithm/Heap4 힙(Heap) 고득점 kit 풀이 완료, 후기 힙으로 우선순위 큐를 구현한다면, 삽입과 삭제가 모두 O(logn)으로 이루어진다. 시간복잡도 계산 시 logn은 거의 상수로 봐도 무방할 정도다. 완전히 상수는 아니지만 n과 비교해도 엄청난 차이임을 알 수 있다. 삽입, 삭제가 원활하게 이루어져야 하는 프로그램에서는 힙구조 우선순위 큐를 이용하면 매우 좋다. C++에서 priority_queue 라이브러리를 사용하는 방법에 대해 포스팅해둔 글이 있으니 참고하면 좋을 것이다. 구조체의 특정 요소(변수)를 기준으로 우선순위를 정하는 방법도 같이 설명해두었다. kimcoder.tistory.com/110?category=887628 삽입, 삭제 모두 O(logn)!! STL priority_queue 소개 priority_queue는 큐에 데이터가 삽입, .. 2020. 10. 8. [Heap, 난이도 중상] 프로그래머즈, 디스크 컨트롤러 본인이 짠 소스 코드의 전체적인 처리 과정은 이렇다. 1. 작업 길이가 짧은 작업을 우선으로 하는 우선순위 큐에 모든 작업들을 push한다. 2. 우선 순위 큐의 top은 가장 작업 길이가 짧은 작업인데, 현재 시간을 기준으로 아직 디스크에 들어오지 않은 작업이라면 당장 실행할 수 없으므로 임시 저장벡터에 빼둔다. 당장 실행할 수 있는 작업이 나올 때 까지 반복해준다. 3-1. 당장 실행할 수 없는 작업이 하나도 없을 수도 있다. 이 때는 앞으로 제일 먼저 들어오는 작업들중 작업 길이가 짧은 작업을 실행해주면 된다. 현재 시간은 이 작업이 끝나는 시간으로 바꿔주면 된다. 3-2. 당장 실행할 수 있는 작업이 있다면 우선 순위 큐의 top에 해당하는 작업을 수행해주고, 현재 시간은 3-1과 마찬가지로 이 .. 2020. 10. 8. [Heap, 난이도 중하] 프로그래머즈, 더 맵게 scoville의 길이 제한이 1,000,000인 것을 보아 힙을 쓰지 않으면 통과할 수 없는 문제라는 것을 알 수 있다. 이 문제 역시 힙의 원리로 돌아가는 priority_queue 라이브러리로 해결하면 쉽게 풀 수 있다. 삽입, 삭제 모두 시간 복잡도가 O(logn)이기 때문에 최고의 시간 복잡도로 해결할 수 있는 것이다. 오름차순으로 정렬하여, pop할 때 가장 작은 원소가 나오게 하였고 이렇게 덜 매운 순위 1,2위를 뽑아서 주어진 공식에 맞게 새로운 스코빌 지수를 계산하여 pq에 push해주는 과정을 반복했다. pq의 top은 최소 스코빌지수를 나타내므로 pq.top()이 K이상일 경우 반복문을 종료하고, pq.top()이 K미만인데 pq에 원소가 1개 이하라면 더 이상 섞을 수 있는 상태가 .. 2020. 10. 7. [Heap, 난이도 중] 프로그래머즈, 이중우선순위큐 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리이다. 삽입, 삭제의 시간 복잡도가 O(logn) 밖에 안된다. 구조를 최대 힙 기준으로 간단히 설명 해보자면 이렇다. 삽입 : 처음에는 힙의 마지막 인덱스에 두고 부모 노드보다 클 경우 계속해서 부모 노드와 swap 해나가면 된다. 삭제 : 힙의 마지막 인덱스를 root에 두고 두 자식 노드들중 큰 값을 가지는 노드와 swap해나가면 된다. 더 자세한 설명이 필요하다면 위키백과를 확인해보면 좋다. ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 .. 2020. 9. 11. 이전 1 다음
