[C/C++] 백준 #1655 가운데를 말해요(힙)
이번 문제는 구간의 중간수 구하던 문제와 같이 두개의 힙을 이용해서 풀 수 있는 문제입니다. 왼쪽은 최대힙(max heap)을 오른쪽은 최소힙(min heap)을 운영합니다. 왼쪽 힙은 오른쪽 힙의 개수보다 1개 크거나 같아야 합니다. 1, 5, 2, 10, -99, 7, 5 순으로 숫자가 불리었고, 이번에 10이 불리는 차례였다면, 왼쪽의 최대힙은 [ 2, 1 ] 이 들어가 있고, 오른쪽 최소힙은 [5]가 들어가 있습니다. 10을 왼쪽힙의 최대값 2와 비교해서 작으면 왼쪽에, 크면 오른쪽에 넣습니다. 이 경우엔 2보다 큰 수이므로 오른쪽에 들어가 있게 됩니다. 그러면 [ 2, 1 ]과 [ 5, 10 ] 이 되고, 두 힙의 크기가 같으니, 힙간 원소 이동은 없습니다. 왼쪽힙의 가장 큰 값을 출력하면 2가..
2022. 9. 22.
백준 #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.
