문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 입력을 정렬한 후 우선순위 큐를 이용하여 처음부터 끝까지 스위핑하여 해결할 수 있는 문제. 일단 입력의 집과 사무실의 위치를 pair arr[100000] 에 저장한다. 어느 쪽이 집이고 사무실 인지는 철로에 영향이 없기 때문에 pair의 first에 더 작은 위치(선의 시작점)를 저장하자. 이제..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 문제마다 이를 구현하는 방식을 제각각이고 고난이도 문제가 많은 편이다. 문제 목록 [LeetCode] Two Sum + 스위핑 기본 문제 [LeetCode] 3Sum+ Two Sum 변형 문제 [백준] 선 긋기(2170) + 스위핑 기본 문제 - Gold 5 [백준] - 철로(13334)★ - Gold 2 [백준] 개구리 점프(17679) + 분리 집합 - Gold 3 [백준] - 버스 노선(10165)★ + 그리디 - Platium 5 슬라이딩 윈도우 [L..

문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 풀이 해당 문제는 -1,000,000,000 이상 1,000,000,000 이하의 범위를 가지는 선들이 주어진다. 따라서 이를 단순히 20억 개의 배열에 저장해서 표현하기에는 메모리 제한으로 불가능하며 비효율적이다. 이 문제는 스위핑 알고리즘 대표적인 문제로 아래와 같은 방법으로 해결 가능하다. 해당 문제에서 일단 배열 points에 입력을 받고 선의 시작 부분을 기준..