알고리즘 공부방

문제 https://www.acmicpc.net/problem/10556 10556번: KAMIONI The first line of input contains the integers N and M (1 ≤ N ≤ 105, 1 6 M 6 105), the number of trucks and the number of pairs of trucks we want to know the number of encounters for. The ith of the following N lines contains the description of the rout www.acmicpc.net 어떤 한 트럭이 수직선 상에서 A1, A2, A3, A4, ... , An (A1>A2A4 ... or A1A3

$N*M$ 크기의 격자에 다음과 같은 두 쿼리가 주어진다. 1. 한 칸의 값을 바꾼다 2. (x1, y1) ~ (x2, y2) 의 합, 최댓값, 최솟값 등을 구한다. 이 문제는 1차원의 문제가 segment tree 를 이용하면 풀리듯이 2D Segment Tree 를 이용하면 풀 수 있다. 하지만 2D Segment Tree 를 사용하면 공간 복잡도가 다이나믹 세그 + 메모리 제한이 빡빡할 경우에는 경로 압축까지 해 주어야 $O(NlogN)$ 이 나오기 때문에 시간, 공간의 측면에서 모두 비효율 적이다. 하지만 이 문제가 오프라인으로 풀 수 있다면 2D Segment Tree 를 구현하지 않아도 더 빠르게 풀 수 있다. 바로 분할 정복을 이용한 것이다. 시간의 흐름에 따라 1, 2번 종류의 쿼리가 하나..

문제 https://codeforces.com/contest/1187/problem/E 트리에서 어떤 노드를 시작으로 선택한 노드들과 인접한 노드들을 골라 검정색으로 칠하는 과정을 계속 반복한다. 이때 노드 하나를 선택할 때 아직 색칠되지 않은 컴포넌트의 크기만큼의 점수를 얻을 때, 점수의 최댓값을 구하는 문제이다. 풀이 가장 먼저, 처음에 선택하는 노드를 하나 정해놓고 생각해보자. 다음에 선택하는 노드는 그 노드와 연결되어 있는 점이어야 하고, 다음에 선택할 점들을 어떤 순서로 골라도 상관이 없다. 이를 이용하면, 다음을 알 수 있다. 루트 하나를 고정시켜 놓은 트리에서, 각 노드마다 서브트리의 크기를 구하면 그 서브트리 크기의 합이 바로 답이 된다. 이는 트리 DP를 이용하여 구할 수 있다. dp[v..

문제 https://oj.uz/problem/view/JOI14_scarecrows 문제 보기 - 허수아비 (JOI14_scarecrows) :: oj.uz JOI 마을에 있는 넓은 황무지에는 $N$명의 신성한 허수아비가 서 있어, 주민들은 일 년에 몇 번씩 허수아비를 둘러싸고 축제를 하고 있었습니다. JOI 마을의 촌장은 "허수아비들의 말씀을 들었다"고 주장하며 황무지에 밭을 하나 만들 계획을 세웠습니다. 허수아비들의 말에 따르면 밭은 다음 조건을 충족해야 한다고 합니다. 각 변이 동서 방향 또는 남북 방향으로 놓인 직사각형이어야 합니다. 남서쪽의 꼭짓점과 북동쪽의 꼭짓점에는 허수아비가 서 있어야 합니다. oj.uz 평면 상에 N개의 점들이 주어져 있을때 다음 조건을 만족하는 점들의 순서쌍의 수를 세는..

문제 https://www.acmicpc.net/problem/7626 직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다. 풀이 이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다. 직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다. 따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다. 이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다. x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다. 따라서 이벤트들을 잘 관리해주는 자료구..

문제 https://www.acmicpc.net/problem/7578 문제를 변형해보면 "Inverse의 수를 세는 문제"로 바꿀 수 있다. 풀이 세그먼트 트리나 BIT 를 사용할 때 많은 경우에 좌표 압축하여 해싱 느낌으로 사용한다. Inverse 의 수를 셀 때도 각 값을 볼때마다, 자기 전에 나온것들 중, 자신보다 큰 것들의 갯수를 카운팅 해준다. 각 수를 인덱스로 하는 배열을 생각해 보면, 각 수를 볼때마다 1. arr[i]~n 까지의 칸들중 등장한 칸의 개수를 세어 준다. -> arr[i]~n 구간의 합을 구한다. 2. arr[i]번 칸에 체크를 해 준다 -> arr[i] 칸에 1을 업데이트 해준다. 두 연산 모두 BIT 연산으로 처리 가능하다. 시간복잡도 : $O(NlogN)$ #includ..

문제 https://www.acmicpc.net/problem/1725 히스토그램에서 얻을 수 있는 직사각형의 최대 넓이를 구하는 문제이다. 풀이 저번에 Divide & Conquer + Greedy 로 $O(NlogN)$ 에 푼 경험이 있는 문제 이다. 하지만 이 문제의 정해는 $O(N)$ 으로 솔브가 가능하며, 바로 스택을 사용한 라인 스위핑이다. i번째 그래프에 대하여 그 그래프를 최소 높이로 가지는 직사각형은 양 끝에 h[i]보다 낮은 그래프를 가질 수밖에 없다. 이를 이용하여 $O(N^2)$ 도 가능하지만, dnc 보다도 못한 결과가 나온다. 여기서도 전에 사용했던 정보를 재활용하면 풀 수 있다. 만약에 아직 자신보다 높이가 낮은 오른쪽 좌표를 결정하지 못한 그래프들이 있다고 하자. 방금 새로운..

문제 https://www.acmicpc.net/problem/1648 N*M 크기의 격자판을 2*1 모양의 타일로 채우는 경우의 수를 출력하는 문제이다. 풀이 일단 당연히 비트마스크 dp 문제이다. 더욱 자세한 풀이는 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648 을 참고하자. 이와 같이 각 칸에 번호를 붙이자. solve(pos, mask) = pos 번째 위치 전까지의 번호는 모두 채워져 있고, 비트마스크가 mask 일때 경우의 수를 의미한다. 비트마스크의 표현 범위는 만약 pos 가 15라면 15~20을 표현한다. 21번부터는 표현할 필요가 없음을 알 수 있다. 왜냐하면 21번을 포함하는 타일이 1~14중 하나를 동시에 포함할 수가..