이 튜토리얼에서는 수직선 위에 놓인 여러 선분들의 합집합(union)의 총 길이를 구하는 프로그램을 작성해 보겠습니다.
각 선분의 시작점과 끝점이 주어졌을 때, 이 선분들이 서로 겹치는 부분을 중복 계산하지 않고 전체가 덮는 구간의 실제 길이를 구하는 것이 목표입니다. 이 문제를 효율적으로 해결하는 대표적인 방법이 바로 클리(Klee) 알고리즘입니다.
클리 알고리즘의 동작 원리
클리 알고리즘은 모든 선분의 시작점과 끝점을 하나의 배열에 모아 정렬한 뒤, 좌표를 순서대로 훑으면서 '현재 몇 개의 선분이 활성화되어 있는지'를 카운터로 추적하는 스위핑(sweeping) 기법입니다. 활성화된 선분이 하나라도 있는 동안에는 인접한 두 좌표 사이의 거리를 결과값에 더해 나갑니다.
문제 해결 절차
- 모든 선분의 좌표 정보를 담은 배열을 초기화합니다.
- 선분 배열 크기의 두 배만큼의 크기를 가지는
points벡터를 준비합니다. 각 요소는 (좌표, 끝점 여부) 쌍으로 저장합니다. - 선분 배열을 순회하면서 다음과 같이 값을 채웁니다.
i * 2번째 인덱스에는 현재 선분의 시작점과false(시작점 표시)를 저장합니다.i * 2 + 1번째 인덱스에는 현재 선분의 끝점과true(끝점 표시)를 저장합니다.
points벡터를 좌표 기준으로 오름차순 정렬합니다.- 카운터 변수를 사용해 정렬된
points벡터를 순회합니다.- 카운터가 0보다 크면, 즉 어떤 선분이 아직 진행 중이라면 현재 좌표와 바로 앞 좌표의 차이를 결과값에 더합니다.
- 현재 지점이 끝점(
true)이면 카운터를 감소하고, 시작점(false)이면 카운터를 증가시킵니다.
- 순회가 끝나면 누적된 결과값을 반환합니다.
구현 예제
지금까지 설명한 내용을 C++ 코드로 구현하면 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
int n = segments.size();
vector<pair<int, bool>> points(n * 2);
for (int i = 0; i < n; i++) {
points[i*2] = make_pair(segments[i].first, false);
points[i*2 + 1] = make_pair(segments[i].second, true);
}
sort(points.begin(), points.end());
int result = 0, count = 0;
for (int i = 0; i < n * 2; i++){
if (count) {
result += points[i].first - points[i-1].first;
}
points[i].second ? count-- : count++;
}
return result;
}
int main() {
vector<pair<int,int>> segments;
segments.push_back(make_pair(1, 3));
segments.push_back(make_pair(2, 7));
segments.push_back(make_pair(6, 12));
segments.push_back(make_pair(13, 5));
cout << segmentUnionLength(segments) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
6
마무리
클리 알고리즘은 시간 복잡도가 O(N log N)으로, 정렬 과정이 전체 성능을 좌우합니다. 선분이 많아져도 효율적으로 동작하기 때문에 구간 합집합 문제에서 널리 활용됩니다. 튜토리얼 내용 중 궁금한 점이 있다면 댓글로 남겨 주세요.