본문 바로가기

전체 글153

[백준/C,C++] 18870번: 좌표 압축 www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 입력된 수열을 오름차순으로 정렬한 후, 압축합니다. 압축할 땐, 넘버링에 쓰일 변수를 유지하며 다음의 원소가 현재 원소보다 크다면 넘버링을 하고 1을 증가 시켜 주고, 아니라면 그대로 유지합니다. 다시 인덱스대로 정렬해야 하기때문에, 초기 입력받을 때 Pair(인덱스, 값)의 형태로 입력받고 값을 기준으로 오름차순 정렬하고 넘버링을 한 후에 다시 인덱스를 .. 2021. 4. 21.
[백준/C,C++] 1655번: 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 생각보다 꽤 어려웠던 문제입니다. 우선순위 큐 2개를 써서 해결할 수 있는 문제인데 핵심은 이렇습니다. 우선 내림차순의 우선순위 큐(pqMin)와 오름차순의 우선순위 큐(pqMax)를 준비합니다. pqMin에는 중간값보다 작은 값들을 담고, pqMax에는 중간값보다 큰 값들을 담습니다. 이때, pqMin을 pqMax의 사이즈와 같거나 1만큼 크게 유지하면, pqMin의 top()은 항상 가.. 2021. 4. 21.
[백준/C,C++] 11286번: 절댓값 힙 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 절댓값 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class AbsMinHeap { private: int heap[MAX]; int idx = 0; public: int size(); bool condition(int child, int parent); void push(int data); int pop.. 2021. 4. 21.
[백준/C,C++] 1927번: 최소 힙 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class MinHeap { private: int heap[MAX]; int idx = 0; public: int size(); void push(int data); int pop(); void swap(int* a, int* b); int select(in.. 2021. 4. 21.

티스토리툴바