백준/스위핑 (5) 썸네일형 리스트형 백준 22876 - 츠바메가에시 https://www.acmicpc.net/problem/22876 해당 문제는 공식 풀이에서 잘 설명하고 있으므로 이 포스트에서는 풀이 방법으로 제시된 indexed heap 풀이의 실 구현을 제공한다. Indexed heap에 대해서는 여기를 참조하라. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 8.. 백준 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 https://www.acmicpc.net/problem/20440 선분 imos법을 통해 모기들의 증감을 관리하여 밀도가 가장 높으면서 긴 구간을 출력하면 된다. 다만 imos법을 사용하면 한 곳에서 여러마리의 모기가 들어왔다 나갈 수 있으므로 가장 긴 구간을 구하기 위해 각 지점에서 발생하는 모기의 출입을 하나의 pair로 합쳐줘야 한다. 본인은 unordered_map을 사용하여 이를 간단히 처리했다. 그 후 다음 과정을 거친다. 1. 모기의 출입을 정리한 후 구간을 스위핑 하면서 현재 저장한 최댓값보다 더 높은 값을 찾았을 때 start를 해당 구간의 시작점, end를 -1로 초기화 한다. 2. 이전까지 모기의 밀도가 최대고 현재 지점의 밀도가 최댓값보다 작아졌을 때 end가 -1이라면 end를 .. [ICPC] 백준 5419 - 북서풍 https://www.acmicpc.net/problem/5419 힌트 더보기 문제에서는 남동쪽 방향으로 가라고 하지만 조건을 생각하면 북서쪽 방향으로 간다고 해도 동일한 결과를 얻을 수 있다. 어떤 섬에 도착했을 때 그 섬과 짝이 될 수 있는 섬의 개수를 효율적으로 셀 수 있겠는가? 이에 대해 감이 잘 오지 않으면 먼저 세그먼트 트리에 대해 공부한다. 풀이 더보기 구간 트리로 다음 구간을 관리한다. 해당 구간에 해당하는 좌표를 가진 섬이 출현한 횟수의 합 이렇게 되면 낮은 좌표를 가진 섬부터 구간에 반영하면서 해당 섬과 연결될 수 있는 섬의 개수를 세주면 가능하다. 그러면 좌표를 정렬해야 할 텐데 어떻게 정렬해줘야 할까? 문제를 보면 무조건 동남쪽 방향으로 섬을 이어야 할 것 같지만 달리 생각하면 북서.. [COCI] 백준 2836 - 수상 택시 https://www.acmicpc.net/problem/2836 관찰 사람을 어떻게 태우던지 목적지에 도착해야 되므로 최소 M만큼의 거리를 이동한다. 어차피 배도 M으로 향해야 하므로 M방향으로 가는 사람들은 무시하고 역방향으로 가는 사람만 고려하면 된다. 역방향으로 가는 사람들은 어떻게 되는걸까? 한번 지나간 곳을 또 지나가는 것은 최적해에 도달할 수 없음을 떠올릴 수 있고 그러면 사람이 오르내리는 사건이 발생하는 최대 구간을 만드는 것을 생각할 수 있다. 최적해에 관한 예시로 5와 7 지점에서 역방향으로 가려는 손님이 있는데 5를 태운 다음 7을 태우지 않고 뒤로 돌아간다면 7을 태우기 위해 다시 그만큼 거리를 이동해야 하므로 최적해가 아님을 알 수 있다. 따라서 스위핑을 통해 역방향 노선을 적절히.. [KOI] 백준 10165 - 버스 노선 www.acmicpc.net/problem/10165 한 노선에 완전히 포함되는 노선은 제외하므로 솔루션은 구간을 검사하는 스위핑에 근간을 두고 있다. 버스 정류장이 원형으로 연결되어 있으므로 각 케이스에 대한 전략과 그 구현이 복잡해진다. Step 1. 문제 접근을 용이하게 하기 위해 각 버스 노선을 두 종류로 분리해보자. 1. 0 을 중간점으로 경유하지 않는 노선 line 2. 0 을 중간점으로 경유하는 노선 circle 1번의 경우 버스 노선이 직선으로 생겼다고 취급해도 된다. 2번의 경우 버스 노선이 N - 1이하의 시작점에서 0번 정류소를 지나가는 형태이다. Step 2. 이 두 종류의 노선에서 3가지의 경우의 수를 통해 어떤 것을 구해야 하는지 파악해보자. 1. line과 line의 비교 li.. 이전 1 다음
