Posts [알고리즘 트레이닝] 4장 - 정렬과 탐색 및 스케줄링(스윕라인, 이벤트, 데드라인)
Post
Cancel

[알고리즘 트레이닝] 4장 - 정렬과 탐색 및 스케줄링(스윕라인, 이벤트, 데드라인)


정렬 알고리즘


  • 실제 상황에서 정렬 알고리즘을 직접 구현할 필요가 있는 경우는 거의 없습니다.
  • 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;
}

[알고리즘 트레이닝] 3장 - 알고리즘의 효율성 추정하기, 최대 부분 배열 합

[React] 회원가입 폼 validation 디자인 구현하기