컴공의 노예생활 컴공의 노예생활

https://www.acmicpc.net/problem/14287 14287번: 내리 갈굼 3 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 이러한 내리 갈굼은 회사에 가장 큰 불만 사항이 되었고, 사장 영선이는 이 불만을 해소해주기 위하여, 단 하루만 야자타임식으로 하여, 반대로 부하가 상사를 갈구면, 그 위로 쭉 사장까지 모두 갈굼을 당한다. 갈굼의 대한 정보는 실시간으로 주어진 www.acmicpc.net 내리 갈굼 2 문제에서 거꾸로 부하가 상사를 갈구는 문제. 상사가 받은 갈굼 정도는 부하들이 받은 내리갈굼의 합과 같다. 전위순..

https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 문제 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다. 모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 www.acmicpc.net 구간합을 구하는 문제는 아니지만 트리에서 자식들의 갱신이 이루어지는 문제이므로 segment tree와 lazy propagation을..

https://www.acmicpc.net/problem/14268 14268번: 내리 갈굼 2 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 이번에는 내리 갈굼이 실시간으로 일어날 것이다. 입력으로 아래와 같은 쿼리가 주어질 것이다. 1 i w : i번째 직원이 직속 상사로부터 w만큼 갈굼을 당한 www.acmicpc.net 앞선 내리 갈굼 문제에서 갱신 중간에 쿼리가 주어지는 문제이다. 내리 갈굼 문제의 알고리즘에서 dfs를 이용하여 해당 사원의 상..

https://www.acmicpc.net/problem/14267 14267번: 내리 갈굼 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 직속 상사와 직속 부하관계에 대해 주어지고, 갈굼에 대한 정보가 주어질 때, 각자 얼마의 갈굼을 당했는지 출력하시오, www.acmicpc.net 갈굼 수치를 입력받을 때, 바로 모든 수치를 전파하는 것은 비효율적이다. 모든 수치를 입력받은 후에, 해당 부모의 수치를 갱신하고 자식에게 전파하는 경우 불필요한 탐색과 ..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 ( www.acmicpc.net 회전 시의 인덱스 변화를 잘 신경쓴다면 어렵지 않은 구현 문제.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 www.acmicpc.net Segment Tree를 이용하여 시간을 단축할 수 있는 문제 아래의 페이지에 설명이 잘 정리되어 있다. https://www.ac..

https://www.acmicpc.net/problem/12766 12766번: 지사 배정 문제 Innovative Consumer Products Company (ICPC)는 비밀 프로젝트를 시작하려하고 있다. 이 프로젝트는 s개의 하위 프로젝트로 구성된다. 이 프로젝트에 관련된 b(≥s)개의 ICPC의 지사들이 있고, ICPC는 각 지사에 하위 프로젝트들 중 하나를 맡기고자 한다. 다시 말하자면, 지사들은 s개의 분리된 그룹으로 나누어지고, 각 그룹이 한 하위 프로젝트를 맡게 된다. 각 달의 마지막에, 각 지사는 그 그룹에 있는 다른 모든 www.acmicpc.net b개의 지사를 s개의 프로젝트로 나누었을 때, 메시지 전달 비용의 최솟값을 구하는 문제이다. 교차로 i에서 j까지의 최단거리를 v[i..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 시간 제한이 짧은 문제인만큼 시간 단축을 위한 아이디어를 떠올리는 것이 중요하다. 핵심 아이디어는 각각의 바이러스가 서로의 전파를 ..