문제 출처: https://www.acmicpc.net/problem/1655 1. 결과 메모리 35032KB, 시간 272ms 2. 풀이 이 문제는 N개의 숫자가 각각 입력될 때마다, 입력된 숫자들 중에서 중간값을 출력해야 한다. 평균값이나 누적 합이 아니기 때문에 각각의 값이 살아서 존재해야 하고, 값이 새로 입력될 때마다 정렬이 수행되어야 중간값을 구할 수 있다. 하지만 값이 추가될 때마다 정렬(sort)이 발생하고, 이런 과정이 N번 반복된다면 시간 복잡도는 커질 수밖에 없다. 이를 더 효율적인 방법으로 풀기 위해서는 최대 힙과 최소 힙을 함께 응용하는 방법이 있다. 우선, 최대 힙과 최소 힙이 의미하는 바를 이해해야 하는데, 최대 힙은 [0] 번째 원소부터 내림차순으로 저장 혹은 출력되는 자료구..
