[알고리즘] 스위핑 Sweeping
문제 풀다가 알게된 새로운 로직이라 정리하게 됐습니다. (본인 공부 및 기록용)😁
Sweeping이란?Permalink
sweeping은 “쓸다”를 의미합니다. 스위핑 알고리즘은 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가며 해결하는 방법입니다. 주로 2차원 평면상의 문제, 기하학적 문제나 이벤트 기반의 문제를 시간 또는 공간적 순서에 따라 처리하는 데 사용됩니다.
알고리즘 과정Permalink
1. 이벤트 기반 처리Permalink
문제를 해결하기 위해 중요한 이벤트들을 정의합니다. 예를 들어, 점의 좌표, 선분의 시작점과 끝점 등이 이벤트가 될 수 있습니다.
2. 이벤트 정렬Permalink
모든 이벤트를 좌표를 기준으로 정렬합니다. 일반적으로 (x,y)로 정렬합니다.
3. 이벤트 처리Permalink
정렬된 이벤트를 순서대로 처리하면서 필요한 작업을 수행합니다. 이 과정에서 데이터를 유지하기 위해 균형 잡힌 이진 탐색 트리나 우선순위 큐 같은 자료구조 또한 이용할 수도 있습니다.
예시Permalink
1. 겹치는 구간 문제Permalink
대표적인 예시로 N 개의 선분이 주어졌을 때, 가장 많이 겹치는 구간의 길이를 구하는 문제입니다. (주차장 점유시간, 사람들 쇼핑하는 시간 등)
n = int(input())
segments = [tuple(map(int, input().split())) for _ in range(n)]
events = []
# 각 선분의 시작점과 끝점을 이벤트로 추가
for l, r in segments:
events.append((l, 1)) # 시작점은 '+1 ' 이벤트로
events.append((r, -1)) # 끝점은 '-1' 이벤트로 정의
# 이벤트를 정렬: 위치가 같을 때는 끝점 이벤트를 먼저 처리
events.sort(key=lambda x: (x[0], x[1]))
max_overlap = 0 # 최대 겹치는 선분의 수
current_overlap = 0 # 현재 겹치는 선분의 수
last_position = None # 마지막 위치
total_max_length = 0 # 최대 겹치는 구간의 총 길이
current_max_length = 0 # 현재 최대 겹치는 구간의 길이
for position, event in events:
if last_position is not None:
# 현재 겹치는 선분의 수가 최대 겹침 수와 같으면 길이를 추가
if current_overlap == max_overlap:
current_max_length += position - last_position
# 현재 겹치는 선분의 수가 최대 겹침 수보다 크면, 최대 겹침 수 갱신해야함
elif current_overlap > max_overlap:
max_overlap = current_overlap
current_max_length = position - last_position
current_overlap += event # 현재 겹치는 선분의 수 업데이트
last_position = position # 마지막 위치 업데이트
total_max_length = max(total_max_length, current_max_length)
print(total_max_length)
궁금한 것들이나 추가 및 수정했으면 좋겠는 거 말해주시면 좋을 거 같아요. 좋은 하루 보내시길 바래요 :)
댓글남기기