응파카 성장일지

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 연산의 개수 n을 입력받는다. 이후 n 만큼의 반복을 실행하는 for 반복문을 만든다. 2. 입력값에 따라 출력 후 값 삭제 or 값 list 에 추가 -> 를 실행한다. 2-1. 0을 입력 받았을 경우 : list 에서 절댓값이 가장 작은 값을 출력한다. 2-1-1. 절댓값이 가장 작은 값이 여러 개일 경우 : 가장 작은 수를 출력한다. - 이를 구현하기 위해 Prio..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Java 의 PriorityQueue 는 기본적으로 최소 힙을 사용한다. PriorityQueue 의 메서드들을 사용할 줄 알면 쉽게 풀 수 있는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue;..

Heap Heap은 완전 이진트리를 기반으로 한다. 최대 힙(Max Heap)은 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다. 최소 힙(Min Heap)은 루트 노드로 올라갈수록 저장된 값이 작아지는 구조이다. 최대 힙이든 최소 힙이든 모든 부모 노드의 우선순위는 자식 노드보다 크거나 같다. 구현의 용이함을 위해 root index는 1부터 시작한다. 위 조건을 만족하며 완전이진트리 형태로 채워나가면 된다. 즉, 형제노드간 우선순위는 고려하지 않아도 된다. Heap의 부모 노드와 자식 노드간 관계 부모 노드의 index = (왼쪽 자식 index) / 2 왼쪽 자식 index = (부모 index) * 2 오른쪽 자식 index = (부모 index) * 2 + 1 새로운 노드 추가 시 새로운 노..