꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/12764 lyzqm님의 포스팅(https://lyzqm.blogspot.com/2018/01/12764.html?showComment=1542815278307#c5681124844879029471)을 참고해서 풀 수 있었던 문제였습니다. 주로 map을 사용하고 set은 사용하지 않았었는데 set이 이진탐색트리 같은 자료구조인 것을 lyzqm님의 게시글을 통해 알게 되었습니다. 알고리즘은 아래와 같습니다.1. pair 배열에 시작 시간과 끝나는 시간 정보를 입력합니다.2. 시작 시간을 기준으로 정렬을 진행합니다.3. 정렬된 순서 순으로 아래와 같이 진행합니다.a. minHeap에 데이터가 존재한다면 현재 사람의 시작 시간보다 이른..

문제 링크입니다: https://www.acmicpc.net/problem/7662 최대 힙과 최소 힙을 priority_queue로 선언하여 풀면 되는 문제였습니다. 알고리즘은 아래와 같습니다.1. 집어넣을 때는 maxHeap과 minHeap 모두 똑같이 집어넣습니다.(집어 넣을 때 {입력 숫자, 인덱스})2. 우선 유효하지 않은 숫자들을 모두 pop합니다.(다른 힙에서 pop된 숫자가 현재 힙의 top에 있을 수 있으므로)3. 2번을 수행한 후 현재 힙의 top의 인덱스가 유효하지 않다고 표시하고 pop합니다.4. 2와 3번을 N번 수행한 후 마지막으로 각각의 힙에 유효하지 않은 숫자들을 pop 시켜줍니다.5. 4번을 수행한 뒤 힙이 비어있다면 EMPTY, 비어있지 않다면 각각의 top을 출력해줍니다..

문제 링크입니다: https://algospot.com/judge/problem/read/RUNNINGMEDIAN 수열의 크기가 정해져있지 않고 초기값과 다음 값의 공식만 주어졌기 때문에 ITES 문제(http://jaimemin.tistory.com/569)처럼 난수 생성기를 통해 숫자를 생성해야하는 문제였습니다.이후에는 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣으면 최대 힙의 root에 중간값이 위치하게 됩니다. 따라서 아래와 같이 불변식을 세웁니다.1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.(수열의 길이가 홀수일 경우 하나 더 큽니다.)2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다. runningMedian 함수가 위 두 조건을 ..