정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/7469 7469번: K번째 수 문제 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. www.acmicpc.net 1. 풀이 merge sort tree + binary search 쿼리마다 각 구간에서 어떤 수 보다 작은 수의 개수가 k-1개 인 것 중 가장 큰 수를 이분 탐색으로 찾는다. 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX = 1 =1;i--){ vector &c = tree..

0. 문제 주소 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 문제 최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DV www.acmicpc.net 1. 풀이 "선반 A번부터 선반 B번까지 A번 ~ B번 dvd가 순서에 상관없이 모두 꽂혀있는 경우" "선반 A번부터 선반 B번까지 가장 작은 dvd 번호가 A, 가장 큰 dvd 번호가 B인 경우" 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX =..

0. 문제 주소 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 문제 2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다. 화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다. 화성 전체 지도를 만� www.acmicpc.net 1. 풀이 스위핑 풀이는 쉽게 이해가 갔다. 문제는 지금까지 유효한 y 좌표를, 즉 0번 이상 덮여져 있는 y 좌표가 얼마나 있는지를 알아야 하는데 update도 구간으로 주어져서 처음에는 lazy propagation을 생각했었다. 이 경우 lazy 배열을 이용한 느린 전파 ~ 0보다 큰 좌표의 개수의 합 연산 사이에서 구현이 어려워졌다. 그래서 구글..

0. 문제 주소 https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 또는 손해를 나타내는 정수 w(-109 ≤ w ≤ 109)가 주어진다. 금광의 좌표는 모두 서로 다르며 w > 0인 금광은 적어도 하나 존재한다. www.acmicpc.net 1. 풀이 1. 좌표의 범위때문에 좌표 압축을 해주어야 한다. 지금까지는 좌표 압축을 너무 원시적으로 했는데, 좋은 테크닉을 찾아서 주워왔다. x좌표, y좌표를 각각 따로 xco, yco 벡터에 저장해둔 ..

0. 문제 주소 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 www.acmicpc.net 1. 풀이 세그트리를 이용해서 맛의 좋고 나쁨을 나타내는 1부터 100만까지의 수에 대해서, 구간 합을 저장하는 세그트리..

0. 문제 주소 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 1. 풀이 inversion 개수를 구하는 문제. 강사님이 merge sort를 구현하면서 inversion을 구할 수 있다고 하셨고, 이해도 갔지만 구현이 어려울 것 같았다. 그래서 ICPC를 준비하며 봤던 내용으로 인덱스 트리 / 펜윅 트리를 이..