백준 #1572 중앙값(힙)
이번 문제는 N개의 데이터가 들어올 때, K개의 연속된 값 구간의 중앙값을 구해야 하는 문제입니다. 일반적으로 N개의 정렬되지 않은 데이터가 주어졌을 때, 중앙값을 구하는 것을 \(O(N)\) 알고리즘으로 가능합니다. N개의 데이터에 K개의 연속된 값 구간은 \(N-K+1\)개가 존재합니다. 만약, 위의 방법으로 하고자 한다면, \(O(NK)\) 알고리즘으로 풀어야 합니다. 그런데 문제에서 N의 최대값을 250,000, K의 최대값은 5,000으로 \(O(NK)\) 알고리즘으로 풀게 되면 시간초과가 될 것이 뻔합니다. https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 ..
2022. 9. 7.
