[BOJ 10167]금광 - D5 문제 설명 2차원 좌표평면상에서 [x좌표,y좌표,가중치]가 한 세트로 이루어진 정보가 N개 주어진다. 우리는 이 좌표평면 상에서 적당한 직사각형을 만들어서 그 직사각형 내부에 있는 가중치가 최대가 되도록 만들면 된다. 문제 풀이 2차원 좌표평면이 나오므로 일단 하나의 축을 기준으로 정렬하고 라인스위핑으로 푸는 방법을 생각했다. y좌표를 오름차순으로 먼저 정렬해놓고, x좌표를 컨트롤 하면 될 것 같다. (반대로 해도 상관없다) 이 문제의 경우에는 먼저 직사각형의 바닥과 천장(y좌표)를 픽스해둔 상태에서, 그 범위 안에 들어오는 x좌표를 왼쪽 -> 오른쪽 방향으로 쭉 저장해놓는다. 이렇게 하고 나면 이 문제를 '가장 큰 연속하는 부분수열의 합' 문제로 바꿀 수..
[BOJ 3392]화성 지도 - P2 문제 설명 N개의 직사각형 좌표(왼쪽 아래, 오른쪽 위)가 주어진다. N개의 직사각형을 모두 겹쳤을 때 총 넓이를 구해야한다. 문제 풀이 직사각형의 좌표값을 입력받을 때, 왼쪽 아래 좌표는 해당 직사각형이 차지하는 y좌표의 불을 켜는 것이고 오른쪽 위 좌표는 불을 끄는 행위라고 생각해보자. 우선 라인스위핑으로 접근하기 위해서 x좌표 오름차순으로 정렬한다. 정렬하고 나면 왼쪽 -> 오른쪽의 순서로 좌표를 살펴보게 되므로 현재넓이는 (현재 x좌표 값 - 지난 x좌표 값) * (높이의 총합) 으로 구할 수 있고, 이 값들을 모두 더하면 전체 넓이를 구할 수 있다. 그러면 이제 '넓이의 총합'을 구하기만 하면 된다. 넓이의 총합은 좌표의 범위에 해당하는 0 ~ 30000 까..
[BOJ 15899]트리와 색깔 - P2 문제 설명 노드가 N개인 트리가 주어진다. 각 노드는 각자 i번의 색깔로 칠해져있다. 그리고 한 가지 쿼리가 주어진다. 쿼리는 a번 노드의 subtree에서 색칠된 색깔의 번호가 b이하인 노드의 개수가 몇 개인지 묻고있다. 모든 쿼리의 정답을 다 더해서 모듈러를 취한 뒤 답하면 된다. 문제 풀이 트리에서 특정 값 x보다 작은 노드의 개수? 이거는 1초의 고민할 필요도 없이 머지소트 트리가 떠올라야 한다. 맨 처음에 제출할 때는 쌩으로 머지소트 트리를 만들었다. 쌩으로 머지소트 트리를 만들면 linear한 트리가 입력으로 주어질 때, 머지소트 트리가 저장해야할 칸이 $O(N^2)$이므로 메모리가 터지게 된다. 따라서 머지소트 트리를 만들기 전에 이 문제를 해결할 전..
[BOJ 2820] 자동차 공장 - P3 문제 설명 N명으로 이루어진 조직에서 트리 구조의 위계와 월급이 주어진다. 그리고 쿼리가 두 종류가 들어온다. 첫 번째는 i번째 사람의 모든 부하의 월급을 x만큼 변화시킨다. 두 번째는 i번째 사람의 월급을 출력한다. 문제 풀이 이 문제의 핵심은 i번 사람의 모든 부하의 월급을 어떻게 빨리 업데이트 하느냐이다. 한명씩 일일이 업데이트 한다면 O(N)만큼의 시간이 소모되므로 시간이 초과된다. 그러면 어떻게든 lazy propagation을 이용해서 log 만에 업데이트 하려는 생각을 했는데, lazy는 연속된 구간만 업데이트 할 수 있다는 한계가 있다. 따라서 불연속적인 트리가 주어진다면 불가능해진다. 그렇다면 여기서 발상을 뒤집어보자. i번 노드의 부하(자식)들을..
[BOJ 2912]백설공주와 난쟁이 - P3 문제 설명 난쟁이가 n명 주어진다. 난쟁이는 각자 하나의 숫자를 갖고 있다. 이어서 쿼리가 주어진다. 각 쿼리는 [l,r]형태로 주어지는데, [l,r] 구간 안에서 난쟁이가 갖고 있는 특정 숫자의 개수가 구간의 길이(r-l+1)의 절반을 초과하는지 묻고 있다. 문제 풀이 특정 숫자의 개수가 구간 길이의 절반을 초과한다면, '반드시' 구간의 절반 경계를 지날 때, 등장하는 수가 같아야만 한다. 단, 역은 성립하지 않는다. 즉 절반의 경계에서 등장하는 수가 같더라도 그 수의 개수가 절반을 초과하지 않을 수도 있다. 따라서 그냥 정답의 '후보'만 된다는 것이고 이는 나중에 실제로 정답인지 검증하는 과정을 거쳐야 한다. 이러한 '후..
[BOJ 11658]구간 합 구하기3 - P5 문제 설명 2차원 grid에서 LeftTop의 좌표 ~ RightBottom의 좌표 사이에 있는 직사각형 형태 안에 포함된 숫자들 모두 더해서 값을 구하거나, 업데이트를 하는 쿼리를 수행한다. 문제 풀이 2차원 세그먼트 트리를 만든다. 기존 세그먼트 트리(1차원) 각각의 노드마다 또다른 세그먼트 트리를 매다는 형태이다. 가로(좌우)형태의 세그 트리를 main으로 짜고 곁가지로 세로(상하)형태의 트리가 달려있다고 생각하면 편하다. 소스 코드 #include #include #include typedef long long ll; using namespace std; const int SIZE = 1030; int tree[SIZE*4][SIZE*4]; int a..
[BOJ 2243] 사탕상자 - P5 문제 설명 1부터 100000까지 라벨이 붙은 사탕이 있다(초기에는 아무 사탕도 없는 상태). 두 가지 쿼리가 들어오는데 첫 번째 쿼리는 k번째로 작은 라벨이 몇 번인지 찾는 것(출력)이고 두 번째 쿼리는 'k번'사탕을 m개 추가하는 것이다. 풀이 [1,1000000]숫자 그대로를 세그먼트 트리의 인덱스로 사용할 것이다. k번째로 작은 라벨이 몇 번인지 찾기 위해서 트리의 i번째 노드는 i번 사탕이 총 몇 개 있는지를 저장하고 있다. 그래서 root 노드에는 결국 전체 사탕의 개수가 담기게 된다. 이제 쿼리에서 루트->리프로 내려갈 때 left child로 내려가면 [1,tree[left]만큼 작은 수가 저장되어 있다는 뜻이다. 따라서 k가 tree[left]보다 크..
[BOJ 1517] 버블 소트 - P5 문제 설명 : n개의 수를 버블 소트할 때, swap이 총 몇 번 일어나는지 세야 한다. 문제 풀이 : i번 째 수를 기준으로 자신의 왼쪽 ( [1, i-1] ) 에 있는 수들 중에서 자신보다 큰 값이 몇 개인지 세면 된다. n이 50만이기 때문에 log 시간만에 세야 한다. 두 가지 풀이가 가능하다. 첫 번째 풀이는 mergesort tree를 이용하면 된다. mergesort tree는 [l,r]구간 상에서 x보다 작은 수의 값을 log만에 구할 수 있다. 이는 얼마 전의 k번째 수 문제에서도 언급했었다. 두 번째 풀이는 바로 offline query를 이용하는 것이다. 이 문제는 쿼리별로 독립시행이다. 즉 이번 쿼리의 정답이 그 이후의 쿼리의 정답에 영향을 끼..