코딩하는 고릴라

🐒 문제 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net 🐈 풀이 1. y좌표 압축 2. x축 정렬 후 x축 방향으로 순차적으로 스위핑 3. 스위핑하며 직사각형의 세로선 활성화 및 비활성화를 통해 좌표상의 직사각형 넓이를 구한다. 1. 주어지는 x, y 좌표의 최대값이 매우 커 이를 바로 활용해 트리를 만들 수 없다. 따라서 좌표 압축을 필요로 한다. 2. 스위핑 기법을 통해 문제풀이를 진행하되, 과연 어떤 값을 어떻게 저장하고 꺼내와야 하는지의 아이디어가 중요..

🐒 문제 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 🐈 문제풀이 핵심 A번 ~ B번 인덱스를 확인했을 때 해당 구간에 A번부터 B번까지의 값이 모두 존재하는지 확인하는 것을 어떤 식으로 구현할지가 관건이다. 이를 위해 해당 구간의 최솟값, 최댓값을 구하여 확인하는 방법을 이용했다. A번 ~ B번 인덱스 구간의 값을 확인했을 때, 최소값이 A이고 최댓값이 B라면 그 둘 사이의 값은 모두 A와 B 사이에 있음을 보장받는다. 따라서 해당 구간의 최솟값, 최댓값만 구..