출처 : https://o-tantk.github.io/posts/finding-median/ 중앙값 찾기 실시간으로 중앙값(Running Median) 찾기 알고리즘
Heap의 두 성질 이용해, 중앙값보다 작은 값들은 Max heap에, 중앙값보다 큰 값들은 Min heap에 저장하는 방식으로 중앙값을 찾는 알고리즘을 구현할 수 있다. 아래의 상황을 보자.  기준은 어차피 가운데에 있으니, 변수를 따로 만들 필요 없이 Max heap 또는 Min heap에 포함시키면 된다. 여기선 Max heap을 이용했다. 3이다.나머지는 기준보다 작다면 Max heap에, 크다면 Min heap에 넣는다. 그리고, Max heap과 Min heap의 크기가 균형되도록 조절한다. 다만, 기준을 고려해 기준을 가진쪽이 하나는 더 클 수 있도록 허용한다. 2는 기준보다 작으니 Max heap에 넣지만 균형을 맞추기 위해 Max heap의
최대값을 이동시킨다. 짝수개이므로 중앙값은 2와 3의 평균이다.4는 기준보다 크니 Min heap에 넣지만 균형을 맞추기 위해 Min heap의 최소값을 이동시킨다. 홀수개이므로 중앙값은 3이다.1은 기준보다 작으니 Max heap에 넣지만 균형을 맞추기 위해 Max heap의 최대값을 이동시킨다. 짝수개이므로 중앙값은 2와 3의 평균이다.입력이 들어올 때마다 한 번의 데이터 이동만으로 실시간으로 중앙값을 찾고 있다. Heap의 시간복잡도가 알고리즘 문제풀이/백준 2020. 3. 19. 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1<=M<= www.acmicpc.net <문제 풀이> 우선순위 큐 수를 입력받을 때마다 중앙값을 찾는 방법은 매 순간 정렬해서 가운데 수를 구하는 방법도 있지만 이는 매 순간 정렬하는데 O(nlogN)이 걸립니다. 최대 힙과 최소 힙을 이용하면 매 순간 정렬하지 않고 O(logN)에 중앙값을 구할 수 있습니다. 아이디어는 중앙값을 기준으로 왼쪽엔 중앙값보다 크기가 작거나 같은 수로 이루어진 최대 힙을 두고, 오른쪽엔 중앙값 보다 크기가 크거나 같은 수로 이루어진 최소 힙을 둡니다. 그리고 홀수 번째 수를 읽을 때마다 중앙값을 힙 사이즈가 작은 쪽에 push 한 뒤, 다시 힙 사이즈가 큰 것에 top을
중앙값으로 하면 됩니다. (중앙값을 기준으로 양 옆에 수의 개수를 일치시키는 느낌) [알고리즘] 1. 최대 힙과 최소 힙을 준비한다. 2. 첫 번째 수를 중앙값으로 한다. 3. 두 번째부터 입력받은 수를 중앙값과 비교해서 작으면 최대 힙, 크면 최소 힙에 push한다. 4. 홀수 번째라면 최대 힙과 최소 힙 중에 사이즈가 작은 힙에 중앙값을 push 하고 그리고 힙 중에 사이즈가 큰 힙의 top을 중앙값으로 한다. <C++ 소스 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
55 56 57 58 #include <iostream> #include <queue> using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test_case;
cin >> test_case; while (test_case--) { int m; cin >> m; int data; int mid; priority_queue<int> max_pq; priority_queue<int, vector<int>, greater<int> > min_pq; vector<int> ans; cin >> data; mid = data;
ans.push_back(mid); //1개 일때는 그 수가 mid for (int i = 2; i <= m; i++) { cin >> data; if (data < mid)max_pq.push(data); //data를 mid 보다 작으면 최대힙 크면 최소힙에 넣는다
else min_pq.push(data); if (i % 2 == 1) { //홀수 번째 수를 읽을 때 마다 int max_pq_size = max_pq.size(); int min_pq_size = min_pq.size(); if (max_pq_size < min_pq_size) { //최대 힙과 최소 힙 중에 사이즈가 작은 힙에 mid를 push
max_pq.push(mid); max_pq_size++; } else { min_pq.push(mid); min_pq_size++; } if (max_pq_size > min_pq_size) { // 힙 중에 사이즈가 큰 힙의 top이 mid가 됨 mid = max_pq.top(); max_pq.pop();
} else { mid = min_pq.top(); min_pq.pop(); } ans.push_back(mid); } } int size = ans.size(); cout << size << "\n";
for (int i = 1; i <= size; i++) { if (i != 1 && i % 10 == 1)cout << '\n';
cout << ans[i-1] << " "; } cout << "\n"; } return 0; } 관련글
|
정렬 없이 중간값 찾기 - jeonglyeol eobs-i jung-gangabs chajgi
관련 게시물
저작권 © 2024 moicapnhap Inc.
