본문 바로가기

Problem Solving/문제풀이

 (89)
백준 11012번 Egg 문제 요약 2차원 좌표 상에서 점이 N개 놓여 있습니다. 그리고 직사각형 쿼리가 주어지는데 해당 직사각형 안에 존재하는 점의 갯수를 구해야 합니다. 좌표의 범위는 최대 10만입니다. 풀이 2차원 세그트리를 만들어서 점들을 기록해 놓는다면 $O(log^2MAX), MAX=10^5$로 해결이 가능하지만 이거를 쌩으로 만들어 버리면 메모리가 $O(MAX^2)$가 필요해서 만들 수가 없습니다. 직사각형 쿼리가 $l, r, b, t$로 들어오는데 이 부분에 대한 구간합을 묻는 것과 동일합니다. tree[x][y]를 x좌표가 [0...x]인 점들 중에서 y좌표가 y인 점들의 개수라고 생각합시다. 그러면 해당 쿼리는 tree[r][b...t] - tree[l-1][b...t]를 묻는 것과 같습니다. tree[x]를 ..
백준 7469번 K번째 수 문제 요약 길이 N일 배열이 주어진다. 쿼리로는 [l,r,k]가 주어지는데 이는 배열 a[i...j]에서 k번째 수를 출력하라는 뜻이다. N은 최대 10만이고 쿼리 수는 최대 5000이다. 풀이 먼저 좌표압축을 하자. 좌표압축을 한 좌표들의 길이로 구간 합 세그먼트 트리를 만들도록 하자. a[1]부터 시작해서 a[N]까지 돌면서 a[i]에 해당하는 위치의 원소를 1씩 늘려줍니다. 이 때, 해당 세그먼트 트리를 PST로 만들어서 i번째 원소를 추가했을 때의 세그먼트 트리에 접근이 가능하도록 합시다. a가 [1,5,2,6,3,7,4]라고 하면 아래와 같이 업데이트가 진행되고 색깔이 바뀌는 부분들만 새롭게 노드를 추가하면 됩니다. 이런식으로 세그먼트트리가 갱신된다고 합시다. i번째 원소를 업데이트한 세그먼트 ..
백준 14176번 트리와 소수 데이터추가로 터졌습니다. 문제 요약 크기 N인 노드가 주어진다. 두 노드를 랜덤으로 골랐을 때 두 노드의 거리가 소수일 확률을 뽑아야 한다. N은 최대 10만이다. 풀이 모든 경로 중에서 경로의 길이가 소수인 경로의 개수를 찾는 문제다. 총 경로의 수는 $\frac{N(N-1)}{2}$이므로 소수인 경로의 개수를 찾고 이것으로 나눠주면 된다. rooted tree에서 root와의 거리가 d인 정점들의 개수를 구한다고 하자. 거리가 d인 정점들의 개수를 구하는 것은 트리를 순회하는 것만으로도 충분하다. 이제 서로 다른 서브트리에 두 노드가 위치해서 root를 지나는 경로를 살펴보려고 하는데 이 경로들을 일일이 전부 확인하려면 $O(N^2)$이 걸린다. 그러나, 이는 두 배열에서 수를 하나씩 골라서 합이 특..
백준 13431번 트리 문제 문제 요약 크기가 N인 트리가 주어진다. 처음에 모든 정점은 흰색이다. 다음과 같은 쿼리를 처리해야 한다. x번 정점을 파란색으로 색칠한다. x번 정점과 모든 파란 정점과의 거리의 합을 계산한다. 풀이 다행히도 파란색이 흰색으로 바뀌는 쿼리가 없다. 각 정점에 대해서 다음과 같은 dp값들을 정의하자. $$ dp(i) = \text{i번 노드를 루트로 하는 서브트리에서 i번 노드부터 파란 정점까지의 거리의 합} $$ 이제 1번 쿼리가 들어오면 x번 정점의 부모를 쭉 타고 올라가면서 부모의 dp값에 부모와 x번 정점간의 거리를 더해주면 된다. 그러나, 부모를 타고 가는 횟수는 최대 N-1번이고 트리가 선형으로 존재하고 리프노드부터 순서대로 타고 올라가면 $O(N^2)$으로 시간 초과가 난다. 이를 막기 위해..
백준 5820번 경주 문제 요약 크기가 N인 트리가 주어진다. 이 떄, 트리에 존재하는 경로 중에서 길이가 K면서 이루는 간선의 수가 가장 작은 경로의 간선 수를 출력하라. 만약에 길이가 K인 경로가 없다면 -1을 출력한다. N은 최대 10만, K는 최대 100만이다. 풀이 rooted tree에서 해당 트리에서 root와의 거리가 d인 정점 중에서 그 경로의 간선 수가 가장 적은 경우의 간선 수를 $min\_depth(d)$라고 합시다. 그러면 이러한 $min\_depth$는 각 서브트리를 순회하면서 갱신이 가능하고, 서브트리를 순회하면서 root와의 거리가 d인 정점을 만났을 때, $min\_depth(K-d)$가 초기값이 아니라 갱신이 되어 있는 상태라면 서로 다른 서브트리에서 root를 지나면서 길이가 K인 경로를 발..
백준 13514번 트리와 쿼리 5 문제 요약 크기 N의 트리가 주어진다. 각 정점은 1번부터 N번으로 숫자가 매겨져 있고, 처음의 모든 정점의 색은 검은색이다. 모든 간선의 길이는 1이며, 무방향 간서이다. 다음과 같은 쿼리를 처리 해야한다. i번 정점의 색을 바꾼다. 흰색이면 검은색으로, 검은색이면 흰색으로 i번과 가장 가까운 흰색 정점과의 거리를 출력한다. N은 최대 10만이고, 쿼리 수도 최대 10만이다. 풀이 트리 DP 형식으로 생각을 해봅시다. $$ dp(i)=\text{i번을 루트로 하는 서브트리에서 i번과 가장 가까운 흰색 정점의 거리} $$ 이런 값들을 잘 관리할 수 있다면 2번 쿼리가 들어왔을 때, 쿼리가 들어온 정점의 부모를 타고 가면서 (부모와 정점 간의 거리) + 부모의 dp값을 비교하면서 답을 찾을 수 있을 겁니다..
백준 16121번 사무실 이전 문제 요약 크기 N인 트리가 주어진다. 그리고 모든 간선의 길이는 1이다. 거주지인 정점이 M개, 후보지인 정점이 K개 주어진다. 원하는 것은 모든 거주지와 모든 후보지 간의 거리의 제곱의 합을 구해야 한다. N은 최대 30만이고 M, K는 둘 다 N만큼 커질 수 있다. 풀이 아무 정점이나 잡아서 그 정점을 루트로 삼은 rooted tree를 생각해보자. 루트의 서브 트리에 속해 있는 거주지와 root와의 거리를 $A_i$라고 하고, 서브트리에 속해 있는 후보지와 root와의 거리를 $B_i$라고 하자. 그러면 거주지와 후보지 간의 경로들 중에서 root를 지나는 경로들의 제곱의 합은 $\sum \sum (A_i+B_j)^2$가 된다. 이를 일일이 다 계산하면 당연히 시간초과를 받는다. 우리가 구해야되는..
백준 20297번 Confuzzle 문제 요약 크기가 N인 트리가 주어진다. 각 정점에는 1부터 N까지의 숫자 중 하나가 적혀있다. 각 간선의 길이는 1이다. 이 때, 같은 번호가 적혀있는 정점 간의 거리 중 제일 짧은 거리를 구해야 한다. N은 최대 10만이다. 풀이 어떤 정점 하나를 잡았다고 하자. 이 정점을 루트로 보면 여러개의 서브트리가 생긴다. 루트 정점에서 특정 번호까지의 최단 거리를 $min\_depth(i)$라고 하자. 그러면 각 서브트리를 순회하면서 $i$가 적혀있는 정점을 만나면 $min\_depth$를 갱신해주고, 만약에 $min\_depth$가 갱신이 되어 있는 상태라면 답도 같이 갱신합니다. 하나의 정점을 루트로 삼고 진행하면 이 과정은 서로 다른 서브트리에서 루트를 지나는 경로들을 봐준 것이 됩니다. 이제 모든 정..

티스토리툴바