스위핑 (Sweep Line)

스위핑이란

스위핑(sweeping)은 데이터를 어떤 기준으로 정렬한 뒤, 가상의 선(sweep line)을 한쪽 끝에서 반대쪽 끝으로 한 번 쓸고 지나가며 답을 갱신하는 기법이다. DP처럼 특정 알고리즘이 아니라 문제를 푸는 틀이다.

전처리: 정렬 O(n log n)
본처리: 한 번의 순회 O(n), 필요하면 힙·트리 같은 자료구조로 "지금 선 위에 걸린 것들"을 관리

그래서 전체 복잡도는 대개 정렬이 지배하는 O(n log n)이다.

그리디와 닮았다. 차이는 그리디가 주어진 순서에서 매 순간 최선을 고르는 데 비해, 스위핑은 그리디하게 훑을 수 있도록 순서를 직접 만든다는 점이다.

언제 떠올리나

신호	예
데이터가 한 축 위에 놓이고 정렬할 수 있다	구간의 시작·끝, 이벤트 시각, 좌표
답이 연속된 영역의 성질이다	가장 많이 겹치는 지점, 합집합 길이, 직사각형 넓이 합
모든 쌍을 비교하면 O(n²)인데 n이 크다	겹치는 선분 쌍, 가장 가까운 두 점

1차원 구간 문제, 회의실 배정, 그리고 2차원 기하 문제에서 자주 나온다.

구간 문제의 기본 부품

구간(interval) 문제는 [[1, 2], [4, 7]]처럼 시작·끝 두 값으로 된 쌍의 배열을 다룬다. 겹치는 경우의 수가 많아 헷갈리지만 부품은 몇 개 안 된다.

부품	코드	설명
시작점 순 정렬	`intervals.sort(key=lambda x: x[0])`	거의 모든 구간 문제의 첫 단계다. 정렬하면 겹칠 수 있는 구간이 이웃하게 된다
두 구간이 겹치는가	`a[0] < b[1] and b[0] < a[1]`	「한쪽이 다른 쪽보다 완전히 앞」이 아니면 겹친다. 끝점이 맞닿는 것도 겹침으로 치려면 `<`를 `<=`로 바꾼다
겹치는 두 구간 합치기	`[min(a[0], b[0]), max(a[1], b[1])]`	정렬 후에는 앞 구간의 시작이 이미 작으므로 끝만 `max`로 늘린다

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:      # 맞닿은 끝점도 합친다
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged

먼저 확인할 조건은 [1, 2]와 [2, 3]처럼 끝점이 맞닿은 구간을 겹친 것으로 보는지, 그리고 [a, b]에서 항상 a < b인지다. 등호 하나가 답을 바꾼다. 경계 사례로는 구간 0개·1개, 다른 구간 안에 완전히 들어간 구간(끝을 max로 갱신하지 않으면 틀린다), 똑같은 구간이 여럿인 경우를 넣는다.

겹치지 않게 남길 수 있는 최대 구간 수(제거할 최소 구간 수)는 끝점 순으로 정렬하는 그리디로 푼다. 회의실 배정과 같은 문제다.

예제 1: 가장 많이 겹치는 선분 수

수직선 위 선분 n개가 주어질 때, 한 지점에서 겹치는 선분의 최대 개수를 구한다. 끝점이 맞닿는 것은 겹침으로 치지 않는다.

시작점 순으로 정렬하고, 지금 겹쳐 있는 선분들의 끝점을 최소 힙에 넣어 둔다. 새 선분을 볼 때마다 이미 끝난 선분(끝점 ≤ 새 시작점)을 힙에서 빼면, 힙에 남은 개수가 그 순간 겹친 선분 수다.

import heapq
 
def max_overlap(segments):
    segments.sort()                      # 시작점 기준 정렬
    ends = []                            # 현재 겹친 선분들의 끝점 (최소 힙)
    best = 0
    for start, end in segments:
        while ends and ends[0] <= start: # 이미 끝난 선분은 내보낸다
            heapq.heappop(ends)
        heapq.heappush(ends, end)
        best = max(best, len(ends))
    return best
 
print(max_overlap([(1, 3), (2, 5), (4, 6), (5, 7)]))  # 2

힙의 top은 "가장 아슬아슬하게 겹쳐 있는", 가장 먼저 끝나는 선분이다. 같은 문제를 이벤트 정렬로 풀 수도 있다. 시작점은 +1, 끝점은 -1 이벤트로 만들어 좌표순으로 정렬하고 누적합의 최댓값을 구한다. 같은 좌표에서는 끝(-1)을 먼저 처리해야 맞닿은 선분을 겹침으로 세지 않는다.

예제 2: 평면을 직선 하나로 나누기

평면 위 점 n개(각각 가치가 있다)를 직선 하나로 둘로 나눠, 양쪽 가치 합의 차이를 최소로 만든다.

평면에는 정렬 기준이 없으니 방향부터 정한다.

두 점을 골라 그 방향을 분할선의 방향 벡터 d로 삼는다. 최적의 분할선은 두 점을 지나는 방향 중 하나로 옮겨 놓을 수 있으므로 이 후보로 충분하다.
각 점을 d에서 떨어진 거리로 정렬한다. 거리는 외적 cross(d, p - p0)로 구한다. 외적은 부호까지 있어 직선의 어느 쪽인지도 알려 준다.
외적 값이 같은 점(분할선과 평행한 같은 줄 위의 점)은 내적 dot(d, p - p0)로 한 번 더 정렬해, 선을 살짝 기울였을 때의 순서를 정한다.
정렬된 순서대로 가치를 누적하며 |전체 − 2 × 누적|의 최솟값을 갱신한다. 분할선을 평행 이동하며 쓸고 지나가는 것과 같다.

방향 후보가 O(n²)개이고 후보마다 정렬 O(n log n)이 들어 전체는 O(n³ log n)이다. 이처럼 스위핑의 비용은 정렬이 지배한다.

  d →                      ← 분할선을 d와 평행하게 유지한 채
 ─────────── cross = 0        cross 값이 작은 쪽에서 큰 쪽으로
   •   •                      한 줄씩 밀어 올린다
 ─────────── cross = 1
     •
 ─────────── cross = 2

구현 팁: 원본 대신 인덱스를 정렬한다

정렬을 여러 번 반복할 때 큰 튜플·객체를 직접 옮기면 비용이 크다. 인덱스 배열을 정렬하고 비교 함수에서 인덱스로 원본을 조회하면 교환 비용이 정수 하나로 줄어든다. 파이썬에서는 sorted(range(n), key=...)가 같은 역할을 한다.

자주 쓰는 조합

조합	쓰임
정렬 + 힙	현재 걸친 구간 관리, 회의실 수 최소화
정렬 + 누적합(이벤트)	동시에 겹친 개수, 구간 합집합 길이
정렬 + 균형 이진 트리·세그먼트 트리	직사각형 합집합 넓이, 선분 교차 판정
각도 정렬(외적 비교)	회전하는 스위프 라인, 볼록 껍질

정리

스위핑 = 정렬로 순서를 만들고 한 번 훑으며 갱신하는 틀
복잡도는 대개 정렬이 지배한다: O(n log n)
"지금 선에 걸린 것"을 힙·트리·누적합으로 관리하는 것이 구현의 중심이다.
2차원에서는 외적으로 정렬 기준(방향·거리)을 만들고, 동점은 내적으로 가른다.

버그 제보