devbelly

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

문제 www.acmicpc.net/problem/5419 알고리즘 스위핑, 세그먼트 트리 풀이 북서풍으로 인해 동쪽과 남쪽에 있는 섬으로만 항해가 가능할 때, 가능한 쌍의 수를 묻고 있습니다. 이전에도 소개했던 문제들 중 inversion count 문제가 있습니다. 그 문제도 inversion이 발생하는 쌍을 count 하는 문제입니다. 브루트 포스로 $O(N^2)$에 해결 가능하지만 세그먼트 트리를 활용하면 $O(NlogN)$에 해결 가능합니다. 이 문제또한 가능한 쌍을 묻고 있으며, 지금까지 지나온 섬들을 세그먼트 트리에 업데이트를 하면 보고 있는 섬마다 $O(logN)$에 지나온 섬의 개수를 알 수 있습니다. 섬을 정렬한 후 순차적으로 쿼리와 업데이트를 진행합니다. x좌표가 같을 때는 y좌표가 큰..

문제 https://www.acmicpc.net/problem/6549 알고리즘 스택 풀이 문제 이름에 이미 문제 내용이 적혀 있습니다. 이와 동일한 문제를 이미 분할정복으로 풀이 한 바 있습니다. 여러 가지 풀이가 가능하므로 이번에는 스택으로 풀어보도록 합시다. 문제에서 주어지는 직사각형 $N$개에 대해 다음과 같은 사각형을 정의하겠습니다. $i$번째 직사각형을 최대 높이로 하고 가장 넓은 사각형을 최대 사각형이라고 합시다. 이 최대 사각형이란 녀석은 다음과 같은 특징을 갖고 있습니다. 이 사각형의 가장 왼쪽과 오른쪽은 $i$번째 직사각형보다 낮은 사각형들로 막혀있습니다. 즉 $i$번째 최대사각형을 막는 제일 왼쪽과 오른쪽을 left [i]와 right [i]라고 할 때, 이들을 구하기 위해선 사각형 ..