devbelly

문제 https://www.acmicpc.net/problem/5899 알고리즘 sweeping 풀이 사각형의 총 넓이를 구하는 문제입니다. 대표적인 스위핑문제입니다. 골드문제여서 $N^2$에 해결할 수 있는 문제입니다. 사각형을 두 개의 선분, 오른쪽 선분과 왼쪽 선분으로 나눕니다. 이후 x좌표를 기준으로 정렬합니다. 왼쪽 선분에 해당하면 set에 넣고 오른쪽 선분에 해당하면 set에서 해당 선분을 제외합니다. set은 지금까지 본 선분들 중에서 아직 넓이를 계산 해야하는 선분들 입니다. 현재 선분과 지금까지 가지고 있는 선분들을 통해 겹치는 y좌표들을 제거하면 중복된 사각형을 제외한 총 넓이를 구할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i <..

문제 www.acmicpc.net/problem/21234 알고리즘 스위핑 풀이 N * N 사각형안에 값들이 주어집니다. 부분 직사각형안에 최솟값이 100이 될 수 있는 직사각형의 갯수를 구하는 문제입니다. 사각형을 결정하기 위해선 상하좌우의 변이 필요합니다. 다르게 말하자면 브루트포스로 해결하기 위해선 $O(N^4)$의 시간복잡도가 필요하므로 시간초과입니다. 한 직사각형의 위와 왼쪽변을 결정했다고 가정하겠습니다. 이 변들을 포함하며 최솟값이 100이 되는 직사각형들을 찾기 위해서는 왼쪽변보다 오른쪽에 위치한 변들을 살피며 그때 아래변들을 살펴보면 됩니다. 이 과정은 위에서 언급한대로 $O(N^4)$의 시간복잡도를 필요하지만 아래변들을 살필 때 우리가 찾는 것은 가장 높은 100의 위치(A)와 포함해서는..

문제 www.acmicpc.net/problem/3392 알고리즘 Sweeping 문제 사각형을 구성하는 좌표들이 주어질 때, 모든 사각형의 면적을 구하는 문제입니다. 단 겹치는 좌표는 한 번만 계산해야 합니다. 각 직사각형을 두 개의 선분으로 분리한 후, x좌표를 기준으로 정렬합니다. 두개의 선분이란 직사각형을 놓았을 때 가장 왼쪽에 있는 선분, 가장 오른쪽에 있는 선분을 의미합니다. 예를 들어 직사각형을 이루는 좌표 (10,10), (20,20)을 받았다면 두 직선은 (10,10,20), (20,10,20)입니다. 앞에서부터 x좌표와 y좌표들입니다. 그리고 순차적으로 각 간선들을 살펴나가며 만약 왼쪽에 있는 선분이라면 그 선분이 가리키는 y좌표들을 업데이트해주고, 오른쪽에 있는 선분이라면 그 선분이 ..