https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 스위핑 + 유니온파인드 문제 X 좌표가 서로 일부 겹치고 있다면 모종의 방법을 통해서 점프해 이동할 수 있기 때문에, 문제의 입력으로 들어오는 Y좌표와 지문의 조건 점프할 때 다른 통나무 위를 지나면 안된다. 를 무시할 수 있다. 이를 무시하고 x좌표만을 사용한 수직선들로 보면 겹치는 부분이 있는 선분들에 대해서 같은 그룹으로 묶어줘야 함을 알 수 있고,..

https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 지문이 이게뭐에요 ㄷㄷ(혼란) 입력으로 들어오는 선분들을 싹 훑으면서(스위핑이다) 진행한다. 현재 이어지고있는 수직선의 구간을 $[s, e]$ 로 저장해 뒀을 때, 새로 입력으로 들어오는 $[x, y]$ 에 대해서 $x > N; for(int i=0; i> a >> b; p.push_back({a,b}); } int ans = 0; int s = p[0].x; int e = p[0].y; for(int i=1; i= p[i].x) e = max(p[..

https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 등수의 차이가 $K$보다 작거나 같으면서 이름의 길이가 같은 친구들의 쌍 갯수를 세는 문제이다. 평범하게 생각하면 $O(N)$으로 훑어가면서 $O(2K)$에 등수의 차이가 작은 구간을 순회하게 되는데, 이 경우에는 $O(KN)$으로 TLE를 받아 제한시간 내에 문제를 해결할 수 없다. 투포인터를 활용한 스위핑으로 문제를 해결했다. 두개의 포인터 $l$ 과 $r$ 을 만드는데, ..

https://www.acmicpc.net/problem/1945 1945번: 직사각형 첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점의 좌표 xbl, ybl과 오른쪽 위 꼭짓점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이 www.acmicpc.net 교내 백준랜덤디펜스 8번. "원점을 지나는 직선" 이 힌트. 어떠한 점(x,y)과 (0,0) 사이 선을 그으면 그 선의 기울기는 y/x 임을 이용한다. 원점에서 그은 어떠한 직선이 직사각형을 지나려면 그 직선의 기울기가 직사각형의 왼쪽 위 꼭짓점에서 그은 선과 직사각형의 오른쪽 아래 꼭짓점에서 그은 선의 기울기 사이에 존재해야한다. 즉, 원점에서 그은 직선을 y=kx라고 ..