스윕 라인 알고리즘 ( Sweep Line Algorithm)

정렬을 이용한 문제풀이

<서문>

무차별 알고리즘을 이용해서 O(n^2) 시간에 문제를 쉽게 풀어낼 수 있는 경우는 많지만 

 

O(n^2)은 입력 크기가 클 때 사용하기에는 너무 느리다

 

O(n^2)이 걸리는 문제를 O(n)이나 O(n log n)시간으로 풀 수 있는 알고리즘의 설계에 대해 알아보자

 

 

 

예를 들어 배열의 모든 원소가 유일한지 검사한다고 해보자

 

아래의 무차별 알고리즘은 두 원소의 모든 조합을 O(n^2)에 살펴보는 것이다

bool ok = true;
for (int i = 0; i < n; i++) {
	for (int j= i+1; j < n; j++) {
    	if (array[i] == array[j]) ok = false;
    }
}

 

 

배열을 정렬한다면 배열에 같은 원소가 있을 때

 

그 원소들이 정렬된 배열에서 나란히 나타나게 되므로 O(n)이면 찾는다.

book ok = true;
sort(array, array+n);
for (int i=0; i<n-1; i++) {
	if (array[i]==array[i+1]) ok = false;
}

 

 

<본문>

정렬을 이용하여 시간 복잡도를 낮추는 스윕 라인 알고리즘에 대해 알아보자

 

스윕 라인 알고리즘은 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링하는 방법이다

 

한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해주면 정답이 구해지는 형태

 

 

예를 들어

 

pc방에 동시에 존재했던 손님 수의 최댓값을 구하는 문제가 있다고 해보자

 

손님은 4명이며 A, B, C, D로 나타냈다.

 

동시에 존재했던 손님 수의 최댓값은 3이며 그 기간은 A가 방문했을 때부터 B가 떠날 때까지다.

 

이 문제를 풀기 위해서는 손님마다 방문과 떠남이라는 이벤트 두 개를 만들어야 한다

 

그리고 이벤트를 시간순으로 정렬하여 차례대로 살펴본다

 

동시에 존재했던 손님 수의 최댓값을 구하기 위해서 카운터 변수를 하나 두는데,

 

손님이 방문하면 카운터의 값을 증가시키고, 손님이 떠나면 감소시킨다.

 

카운터의 최댓값이 동시에 존재했던 손님의 최댓값이며

 

이 알고리즘의 수행 시간은 O(n log n)이다.

 

 

 

 

백준에서 예시문제를 풀어보자.

 

 

예시문제

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

백준-선긋기

 

 

해설은 이 블로그 참고

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220907708368 

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)