정렬 알고리즘
- 실제 상황에서 정렬 알고리즘을 직접 구현할 필요가 있는 경우는 거의 없습니다.
- C++에서 잘 정의된 STL 라이브러리의 sort 를 활용할 수 있습니다. (헤더파일 algorithm)
- sort 함수는 C++11 표준에서 O(n log n)으로 동작해야 한다고 규정하고 있습니다.
정렬을 이용한 문제 풀이
스윕 라인 알고리즘(Sweep line algorithm)
스위핑 기법(Sweeping algorithm), 라인 스위핑(Line sweeping) 이라고도 불리는 이 알고리즘은 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링하는 방법입니다.
기법 자체는 간단하지만 문제들은 대부분 어려운 편에 속한다고 합니다.
예 : 백준 2170번 : 선 긋기
스윕라인이란 어떤 선이나 공간을 한쪽에서부터 쭉 훑어 보는 것인데, 이 때에는 정렬된 요소가 중요하게 됩니다.
백준 선 긋기 문제가 스윕 라인을 적용할 수 있는 문제 중 하나입니다.
이 문제는 점의 좌표가 약 20억개가 주어지기 때문에, 절대로 20억 칸의 배열을 만들거나 할 수는 없습니다.
그래서 스윕 라인 알고리즘으로, 요소들을 정렬한 뒤 한 쪽에서부터 한번에 쭉 살펴봐야 합니다.
문제에서는 선을 여러 개 그을 수 있는데, 이미 선을 그은 곳 위에 겹쳐서 그릴 수도 있습니다.
그러나 여러 번 그은 곳과 한번 그은 곳의 차이는 구별할 수 없습니다. (선이 여러번 그려진 곳은 한 번씩만 계산)
이 때 그려진 선들의 총 길이를 구하는 프로그램을 작성해야 합니다.
문제의 예제 입력대로 선을 나타내 보면 위 그림과 같을 것입니다.
위에서 겹쳐진 구간인 [2, 3] 과 [3, 5] 는 한 번씩만 계산되어, 선 [1, 5] 하나로 나타나는 것입니다.
생각한 아이디어
이어졌거나 겹치는 선분들끼리는 한 구간으로 합쳐서, 최종 결과로 다 합쳐지고 남은 구간들의 길이들을 세서 더하면 답이 될 것입니다.
이 문제에서 주어진 구간들을, 왼쪽 끝 좌표 순서대로 먼저 정렬합니다.
- 그리고 이렇게 정렬된 순서대로 구간들을 차례로 살펴 봅니다.
- 현재 구간이 이전과 합쳐질 수 있으면, 이전 구간에 합칩니다.
- 이렇게 처음부터 끝까지 O(n) 시간으로 살펴보면 문제를 풀 수 있습니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int, int> pi;
const int INF = 1e9 + 1;
int main() {
pi arr[1000000]; // 최대 100만개까지의 선을 수용하기 위해
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int a, b;
scanf("%d %d", &a, &b);
arr[i].first = a; arr[i].second = b;
}
sort(arr, arr + N); // first pair의 오름차순으로 정렬됨
int temp = 0;
int result = 0, l = -INF, r = -INF;
// [l, r] - 현재 합치는 중의 구간 [l, r]
for (int i = 0; i < N; i++) {
// 현재 선의 첫 시작점이 지금 구간의 오른쪽 끝점 r보다 작으면 합칠 수 있음
if (arr[i].first < r) {
r = max(r, arr[i].second);
}
// 합칠 수 없으면, 지금까지의 값을 저장하고 새로운 선으로 [l, r] 구간을 설정함
else {
result += r - l;
// 새롭게 l, r 설정
l = arr[i].first;
r = arr[i].second;
}
}
// 마지막 선은 l, r은 설정되지만 그것을 더한 결과값은 계산되지 못하므로 마저 계산해 준다.
result += r - l;
printf("%d", result);
return 0;
}
- 스윕 라인 알고리즘을 활용하는 문제들(백준)
- 선 긋기(2170번) : https://www.acmicpc.net/problem/2170
- 북서풍(5419번) : https://www.acmicpc.net/problem/5419
- 원 영역(10000번) : https://www.acmicpc.net/problem/10000
- 화성 지도(3392번) : https://www.acmicpc.net/problem/3392
- 가장 가까운 두 점(2261번) : https://www.acmicpc.net/problem/2261
- 해당 포스팅은 여기 (네이버 라이(kks227)님 블로그)를 참조하여 작성하였습니다.