궤도

문제 풀이 이 문제의 시간 제한은 0.1초다. 그니까 입력이 들어오자마자 바로바로 출력을 내보내야 한다는 것이다. 입력을 받을 때를 제외하곤 단 하나의 for문도 쓸 수 없다. 그럼 도대체 제일 작은 값도 제일 큰 값도 아닌 중앙값을 바로바로 내보낼 것인가... 중앙값을 기준으로 그보다 작은 수는 최대 힙에 넣고 그보다 큰 수는 최소 힙에 넣는 것이다. 그렇다면 최대 힙의 top에는 중앙값보다 같거나 작은 수 중 가장 큰 수가, 최소 힙의 top에는 중앙값보다 같거나 큰 수 중 가장 작은 수가 올 것이다. 균형을 이루기 위해선 최대 힙과 최소 합의 원소의 갯수 차이가 0(원소의 총 갯수가 홀수)이거나 1(원소의 총 갯수가 짝수)이여야 한다. 만약 이 균형이 깨진다면 중앙값을 수정해야 한다. 위 상태에서 ..

문제 풀이 myunji.tistory.com/271 [백준] 11279번 : 최대 힙 문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe.. myunji.tistory.com myunji.tistory.com/272 [백준] 1927번 : 최소 힙 문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 ..

문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 그 반대인 greater로 바꿔주면 최소 힙이 되겠다. 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //greater면 min heap int N, x; cin>>N; for(int i=0;i>x; if(x==0){ if (pq.empty()) cout

문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //default : max heap i..