[CF 1667A] Make it Increasing - 1300 Problem - A - Codeforces codeforces.com 문제 설명 길이가 n인 배열 a가 주어지고, 모든 원소가 0인 길이가 n인 배열 b가 있다. 이때 $b_{i}$에서 $a_{i}$를 원하는 만큼 더하거나 빼는 연산을 할 수 있다. 배열 b를 중복 없이 증가하는 수열로 만들고자 할 때 필요한 최소 연산의 수를 구하시오. 문제 풀이 N의 크기가 5000밖에 되지 않기 때문에 $N^2$풀이를 생각해볼 수 있다. $N^2$이라면 고정된 i에 대한 최솟값을 $N$만에 구하고, i를 [1, N]에 대해 다 돌려보면 된다. 고정된 i의 위치의 값은 0이고, 그 양 옆 범위인 [1,i-1], [i+1,N]의 범위만 조작하면 된다. ..
Centroid of Tree centroid란 트리에서 어떤 노드(와 연결된 엣지들)를 삭제했을 때, 분리된 component의 크기가 n/2 이하가 되는 노드를 말한다. centroid는 트리에서 반드시 최소 하나는 존재하며, 최대 2개를 가질 수도 있다. centroid를 찾는 방법은 두 번의 dfs를 돌려보면 된다. 첫 번째 dfs(subtreeDFS) 에서는 어떤 임의의 노드 x를 트리의 루트라고 가정하고 dfs를 시작한다. x 노드의 subtree가 갖고 있는 노드의 개수를 subtree[] 배열에다가 저장해놓는다. 두 번째 dfs(findCentroid) 에서는 구해놓은 subtree[]값을 통해 현재 노드 i를 삭제했을 경우, 그로 인해 분할되는 component들(subtree)의 값이 ..
2021 shake! 출제 및 운영 후기
지난 1월 15일, '2021 경인지역 6개대학 연합프로그래밍 경시대회'인 shake! 가 열렸다. 지금 글을 쓰는 시점과는 시간이 꽤 흐르긴 했는데 나름대로 고통스러운 흥미로운 경험을 하기도 했고, 회고할 만한 일도 있었다고 생각하기에 지금이 되어서야 후기를 남기게 되었다. 배경 내가 소속된 아주대학교 소학회 A.N.S.I.는 2015년부터 shake! 대회를 주관하고 있다. 내가 입학한 2017년 이전에는 잘 모르겠지만, 2017년 이후로는 A.N.S.I.의 회장이 shake!의 대회 운영을 맡는 게 관례였다. 다만 회장이 shake! 대회에 참가를 하게 되는 경우, 운영 과정이 매끄럽지 않을 수도 있다는 점이 우려되어 이런 경우에는 별도의 인원이 대신 대회 운영을 맡을 수밖에 없었다. 이번 대회가 ..
[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번 노드의 부하(자식)들을..