프로그래밍 공부 노트

https://www.acmicpc.net/problem/2024 2024번: 선분 덮기 각 테스트 케이스는 M(1 ≤ M ≤ 50,000) 과 "Li Ri"(|Li|, |Ri| ≤ 50,000, i ≤ 100,000)쌍으로 구성이 된다. 각각은 다른 행으로 분리되어 있다. 입력은 "0 0"으로 끝난다. 모든 입력은 정수이다. www.acmicpc.net 문제 설명만 보면 단순한 라인 스위핑 문제로 착각하기 쉽지만, 사실 이 문제는 일반적인 라인 스위핑처럼 모든 선을 사용하는 문제가 아니다. 예를 들어 두 선 [3, 5]와 [3, 8] 중 한 가지 선분을 사용할 경우 선 [3, 8]을 사용하는 것이 반드시 이득이다. A < P < B일 때, 구간 [0, A]에서 시작하는 선들을 이용해 구간 [0, B]를..

https://www.acmicpc.net/problem/23349 23349번: 졸업 사진 첫째 줄에 학교가 공지할 것으로 예상되는 혼잡 (장소, 시간대) 쌍을 공백으로 구분하여 출력한다. 이때 시간대는 조건을 만족하는 가장 긴 시간대를 의미한다. www.acmicpc.net 각 촬영을 선분, 촬영의 시작 시간과 종료 시간을 시작점과 끝점으로 보면, 이 문제는 라인 스위핑을 이용해 선분이 가장 많이 겹치는 구간을 찾는 문제이다. 이 때 촬영 장소, 즉 선분의 종류가 문자열로 구분되므로, 라인 스위핑을 위해 각 점을 정렬할 때 선분의 종류를 최우선으로 두어 정렬하면 각 종류 별로 선분을 나누어 저장할 필요 없이 빠르게 라인 스위핑을 실행할 수 있다. #include #include #include #in..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 라인스위핑 기법을 사용한다. 이 때 입력이 정렬된 순서대로 주어지므로 입력을 정렬하지 않고, 각 선분의 시작점과 끝점을 기존 선분의 끝점의 최댓값과 비교해 입력받은 선분과 기존에 존재하던 선분이 겹치지 않는 부분의 길이만을 더한다. #include using namespace std; #define MIN_X -1000000000 int max(int a, int b) { return a > b ? a : b; } int main() { // 입출력..

라인 스위핑은 수 직선 위의 여러 선분이 겹쳐있을 때, 이 선분을 모두 겹친 경우의 길이를 측정하는 알고리즘이다. 선분을 입력받을 때마다 그 길이를 측정해 합을 구한다면 선분이 겹쳤을 때 에러가 발생하므로 불가능하고, 선분을 입력받을 때마다 배열에 선분을 그린 뒤 길이를 센다면 선분의 길이 n에 대해 각 선분을 표시할 때의 시간 복잡도가 O(n)이므로 선분이 매우 길거나 선분의 개수가 매우 많다면 시간을 너무 오래 소모하게 된다. {int crd, int stat}꼴 구조체의 배열 arr에 선분을 입력받을 때마다 {시작 좌표, 1}과 {끝 좌표, -1}을 push한 뒤 좌표가 증가하는 순으로, 좌표가 같다면 시작 좌표가 앞에 오게끔 정렬한다. 이후 arr을 0번째 인덱스부터 순차적으로 탐색하며 stat ..

https://www.acmicpc.net/problem/24229 24229번: 모두싸인 출근길 취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있 www.acmicpc.net 각 판자의 시작점을 pair{ 시작점의 좌표, 1 }, 끝점을 pair{ 끝점의 좌표, -1 } 꼴로 배열에 저장해 정렬하고, 좌표가 같은 pair는 second를 모두 더해 압축한 꼴로 저장한다. 이렇게 하면 각 좌표에서 (시작점의 개수 - 끝점의 개수)를 오름차순으로 정렬된 꼴로 얻을 수 있으므로, 라인스위핑을 이용해 문제를 해결할 수 있다. 우선 문제의 조건을 보면 좌표 0에서 시작하..