Sweeping

Sweep?

---

Sweep은 영단어로 쓸다, 휩쓸다 라는 뜻을 가지고 있다. 무언가가 한쪽방향으로 휩쓸고 지나가는 이미지를 생각하면 된다.

이 문제 풀이 기법은, 어떠한 요소들을 일렬로 정렬 해둔 뒤 쓸어내는 방식으로 문제를 푸는 모습을 보인다.

간단한 예시 문제를 하나 알아보자.

수직선 상의 점 10만개가 랜덤한 순서로 주어졌다면, 그 점들 사이 간격 중 가장 짧은 간격은 어떻게 구할까?

점의 개수가 10만 개라면, 단순한 $O(N^2)$ 풀이법으로는 이를 해결할 수 없다. 하지만 만약 (A, B, C) 점 세 개가 순서대로 나열되어있는 경우를 보자. 우리가 |AC| 선분의 길이를 알아야 할까? 어짜피 |AB| 아니면 |BC|가 정답일 것이다.

스위핑의 핵심 통찰은. 전체를 통으로 보려하지 않고 한쪽으로 흘러가며 의미있는 정보만 처리하는 것 이다.

예시 코드 (C++)

---

예시 문제를 기준으로 설명 하면, 스위핑은 일단 한 쪽 (하나의 축) 으로 흘러가기 위해서 입력값들을 정렬 해야 한다.

vector<int> input(5) = {1, 4, 2, 4, 6};
sort(input.begin(), input.end());
// input = [1, 2, 4, 4, 6]

이제 가장 짧은 구간을 알려면, 정렬되어있는 입력값들에게서 input[i] - input[i - 1], input.size() > i > 0 만 계산하면, $O(N)$ 으로 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
 
int solve(const vector<int>& input) {
	sort(input.begin(), input.end());
	
	int ans = INT_MAX;
	for(int i = 1; i < input.size(); i++) {
		ans = min(input[i] - input[i - 1]);
	}
	
	return ans;
}

스위핑을 떠올릴 수 있는 단서들

---

스위핑이 자연스럽게 어울리는 문제들은 특징이 있다.

1. 시간이나 좌표축이 문제의 자연스러운 기준이 될 때
   • 예: 이벤트가 특정 시점에 발생하고, 그 전후로 상황이 달라질 때.
   • 예: x축을 기준으로 점이나 선분이 등장하거나 사라지는 경우.
2. 전체보다 국소적 관계가 중요할 때
   • 예: 가장 가까운 점은 멀리 있는 점과는 상관이 없고, 현재 근처에 있는 점들과만 비교하면 충분하다.
3. 등장과 소멸이 있는 객체를 다룰 때
   • 예: 구간이 열리고 닫히는 시점, 선분이 스윕선과 교차하는 순간.

이런 단서가 보이면, “혹시 스위핑으로 단순화할 수 없을까?”라는 질문을 던져보면 좋다.