정렬된 데이터를 순차 탐색하는 스위핑 (Sweeping)

스위핑 알고리즘이란

스위핑(Sweeping) 알고리즘은 주어진 문제에서 구간이나 이벤트를 순차적으로 처리하여 결과를 도출하는 알고리즘 기법이다. 이 기법은 특히 구간 합 문제, 이벤트 처리 등과 같은 문제에 유용하게 적용된다. 스위핑 기법은 기본적으로 주어진 구간이나 사건들을 일정한 기준에 따라 정렬한 뒤, 이를 하나씩 처리하는 방식으로 동작한다. 이를 통해 겹치는 구간을 병합하거나, 특정 구간에 해당하는 값을 누적하는 등의 작업을 효율적으로 수행할 수 있다.

동작 과정

스위핑 알고리즘은 보통 다음과 같은 순서로 동작한다.

데이터 정렬: 먼저, 주어진 구간들을 시작점을 기준으로 정렬한다. 오름차순으로 정렬하는 것이 일반적이며, 시작점이 모두 같다면 끝점을 기준으로 정렬할 수 있다.
순차 탐색(반복) : 정렬된 구간을 차례대로 확인하며, 현재까지 진행한 구간과 비교한다. 각 구간을 처리하면서 겹치는 구간을 병합하거나 새로운 구간을 시작하는 방식으로 진행된다. 만약 현재 구간이 이전 구간과 겹친다면, 그 구간을 병합하여 새로운 구간을 형성한다. 반대로 겹치지 않으면 이전 구간의 결과를 계산하고, 새로운 구간을 시작한다.
최종 결과 도출: 모든 구간을 처리한 후, 마지막에 남은 구간에 대한 결과를 추가적으로 계산하여 최종 결과를 도출한다. 이 과정에서 구간의 길이나 합을 계산할 수 있다.

이 과정은 구간의 개수나 크기에 관계없이 일관된 방식으로 진행되며, 구간을 처리하는 데 있어서 불필요한 중복 계산을 방지할 수 있다.

스위핑 예시 코드

import sys
input = sys.stdin.readline
INF = int(1e12)

n = int(input())  # 구간의 개수
data = [tuple(map(int, input().split())) for _ in range(n)]  # 구간 정보 입력
data.sort()  # 시작점 기준으로 구간 정렬

result = 0  # 결과를 저장할 변수
start, end = -INF, -INF  # 현재까지의 구간 시작점과 끝점

for a, b in data:
    if a > end:
        result += end - start  # 이전 구간의 길이를 결과에 더함
        start, end = a, b  # 새로운 구간으로 업데이트
    else:
        end = max(end, b)  # 겹치는 구간이 있으면 끝점을 확장

result += end - start  # 마지막 구간 길이 더하기
print(result)

이 코드는 구간의 개수에 대해 O(n log n)의 시간 복잡도를 가지며, 효율적으로 문제를 해결할 수 있다.

정렬된 데이터를 순차 탐색하는 스위핑 (Sweeping)

SERIES: 알고리즘 (10)

스위핑 알고리즘이란

동작 과정

스위핑 예시 코드

추천 문제