자료구조 (2) 썸네일형 리스트형 백준[Python] - 7662 : 이중 우선순위 큐 문제 이중 우선순위 큐 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 우선순위 큐, 즉 heap 자료구조는 일반적으로 '최소 힙'과 '최대 힙'으로 구성된다. 이에 대한 추가적인 설명은 자료구조 - 힙 을 참고하길 바란다. 하지만, 해당 문제에서는 최대, 최소에 대한 두개의 우선순위를 가지는 큐를 구성해 연산을 진행해야 한다. 그렇기 떄문에 일반적인 방법으로 heap을 생성해서는 문제를 제한시간 내에 해결할 수 없다. 일반적으로 드는 생각은 최대 힙, 최소 힙을 둘다 생성해 'D 1'일 경우에는 최.. 자료구조 - 힙(Heap) 힙(Heap)이란? '완전 이진 트리'의 한 종류로, 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 자료구조 완전 이진 트리란? 포화 이진 트리에서 오른쪽 부터 잎이 제거된 형태의 트리 자료구조 왼쪽 노드부터 채우는 형식 이진트리의 특성상, 부모 노드와 자식 노드간의 관계에는 일정한 규칙이 존재한다. a라는 리스트가 있다고 가정할 때, a[i]의 자식 노드는 a[2i], a[2i+1]에 존재한다. a[j]의 부모 노드는 a[j//2]이다. 힙의 종류는 대표적으로 2가지가 존재한다. 최소 힙 부모 노드가 자식 노드보다 반드시 작은 값을 가져야 하는 힙 구조 최대 힙 부모 노드가 자식 노드보다 반드시 큰 값을 가져야 하는 힙 구조 ex) 13, 88, 112, 35, 49, 17 이 입력값으.. 이전 1 다음