2차원 평면 위에 수백만 개의 선분이 무작위로 흩뿌려져 있다고 상상해 보십시오. "이 선분들이 겹치는 구간의 총길이는 얼마인가?" 혹은 "가장 많은 선분이 동시에 겹치는 지점은 어디인가?"라는 질문을 받았을 때, 모든 선분을 서로 일일이 대조하는 O(N^2)의 브루트 포스(Brute Force) 방식을 사용한다면 컴퓨터는 영원히 답을 내놓지 못할 것입니다. 이러한 기하학적 문제나 겹치는 구간(Interval) 최적화 문제를 마법처럼 O(N log N)의 선형 로그 시간으로 해결해 내는 기법이 바로 '스위핑(Sweeping)' 알고리즘입니다. 마치 바닥을 빗자루로 쓸고(Sweep) 지나가듯, 가상의 세로선을 왼쪽에서 오른쪽으로 쭉 이동시키며 만나는 이벤트들을 순차적으로 처리하는 이 우아하고 직관적인 알고리즘의 원리를 낱낱이 파헤쳐 보겠습니다.
1. 스위핑 알고리즘의 핵심: "정렬(Sorting)이 9할이다"
스위핑 알고리즘은 복잡한 자료구조나 난해한 점화식을 요구하지 않습니다. 이 알고리즘의 본질은 데이터를 '특정 기준(주로 X좌표 또는 시간)에 따라 오름차순으로 완벽하게 정렬'해 두고, 한쪽 방향으로만 스캔하면서 문제를 해결한다는 데 있습니다. 정렬에 O(N log N)의 시간이 소요되며, 이후 스캔 과정은 단 한 번의 O(N)으로 끝나기 때문에 전체 시간 복잡도가 극적으로 단축됩니다.
2. 실전 응용 1: 선분 겹침 문제 (Merge Intervals)
가장 고전적인 코딩 테스트 유형인 '선분 덮기' 또는 '회의 시간 겹침' 문제를 스위핑으로 풀어봅시다. 여러 개의 선분 [시작점, 끝점]이 주어졌을 때, 겹치는 부분을 하나로 병합하여 총 덮인 길이를 구하는 로직입니다.
2-1. 시작점을 기준으로 정렬하라
먼저 모든 선분을 '시작점(Start)'이 작은 순서대로 오름차순 정렬합니다. 만약 시작점이 같다면 '끝점(End)'이 작은 순서대로 정렬합니다. 이렇게 정렬해 두면, 가상의 수직선이 왼쪽에서 오른쪽으로 훑고 지나갈 때 선분들을 순서대로 만나게 됩니다.
2-2. O(N) 병합 시뮬레이션
정렬이 끝났다면, 첫 번째 선분을 기준점(현재 병합 중인 선분)으로 잡고 다음 규칙을 적용합니다.
- 겹치는 경우 (다음 선분의 시작점 ≤ 현재 선분의 끝점): 두 선분은 하나의 긴 선분으로 합쳐질 수 있습니다. 이때 새로운 선분의 끝점은 현재 선분의 끝점과 다음 선분의 끝점 중 더 큰 값(Math.max)으로 갱신해 줍니다.
- 겹치지 않는 경우 (다음 선분의 시작점 > 현재 선분의 끝점): 두 선분은 완전히 분리되어 있습니다. 기존에 병합하던 선분을 결과 리스트에 저장해 두고, 방금 만난 새로운 선분을 새로운 기준점으로 삼아 탐색을 계속 이어갑니다.
이 단순한 비교만으로 수백만 개의 겹치는 선분들을 깔끔하게 단일 선분들로 병합해 낼 수 있습니다.
3. 실전 응용 2: 동시 접속자 수 구하기 (이벤트 분리)
"수많은 사용자의 접속 시작 시간과 종료 시간이 주어졌을 때, 동시 접속자가 가장 많았던 순간의 인원은 몇 명인가?"라는 문제도 스위핑의 강력한 무대입니다. 이 문제는 선분을 병합하는 것이 아니라 '점(Point)의 이벤트'로 분리하여 접근해야 합니다.
3-1. 들어옴(+1)과 나감(-1)의 논리
사용자 A가 [1시 접속, 5시 종료]를 했다면, 이를 선분 하나로 두지 않고 두 개의 이벤트로 쪼갭니다.
1. 이벤트(시간: 1, 상태: +1명)
2. 이벤트(시간: 5, 상태: -1명)
모든 사용자의 데이터를 이렇게 두 개의 이벤트로 쪼갠 뒤, '시간'을 기준으로 오름차순 정렬합니다. 이제 빗자루(스위핑 라인)로 이 이벤트 배열을 순차적으로 쓸고 지나갑니다. 접속 이벤트(+1)를 만나면 현재 접속자 변수에 1을 더하고, 종료 이벤트(-1)를 만나면 1을 뺍니다. 이 과정 속에서 접속자 변수가 도달했던 최댓값(Max)을 기록해 두기만 하면, 복잡하게 구간 트리(Segment Tree)를 짤 필요 없이 O(N log N)만에 완벽한 정답을 추출할 수 있습니다.
1. 스위핑(Sweeping) 알고리즘은 데이터를 특정 축(X좌표, 시간)을 기준으로 정렬한 뒤, 한쪽 방향으로 훑으며(Scan) 겹침 등의 이벤트를 처리하는 O(N log N) 최적화 기법입니다.
2. 선분 병합 문제에서는 시작점 기준 정렬 후 이전 끝점과 다음 시작점을 1:1 비교하며 O(N)으로 구간을 합쳐나갑니다.
3. 최대 중첩(동시 접속자) 문제에서는 시작과 종료를 분리된 이벤트(+1, -1)로 취급하여 정렬한 뒤, 값을 누적해가며 최댓값을 찾는 방식으로 우아하게 해결합니다.