본문 바로가기

Problem Solving/문제풀이

 (89)
백준 14858번 GCD 테이블과 연속 부분 수열 문제 요약 $G[i][j]$에 $GCD(i,j)$가 저장되어 있는 크기 $N \times M$의 배열이 있다. 길이 $k$인 수열 $a_1, a_2, ... a_k$가 주어졌을 때, 배열 G에서 연속한 부분 수열들 중에서 $a_1, a_2, ... , a_k$가 존재하는지 아닌지를 구해야 한다. 조건은 $1 \le N,M \le 10^{12}, \; 1 \le i \le N, \; 1 \le j \le M, \; 1 \le k \le 10000$이다. 문제 풀이 일단 첨자표시가 마크다운에선 좀 쓰기 힘드니 $G[i][j]$대신 $G(i,j)$로 쓰겠다. 문제를 다시 적어보자면, $1 \le l \le k$인 $l$에 대하여 $G(x,y+l) = a_l$인 $(x,y)$를 찾는 것이라고 생각하면 된다. 여..
백준 10755번 컴퓨터실 문제 요약 COI 2015 3번 문제이다. 현재 기준으로 솔브드 티어는 다이아 4다. 1부터 M까지의 숫자가 부여된 자리가 순서대로 일직선 상에 놓여 있고, 이미 차 있는 자리가 N개 주어진다. 그리고 M-N개의 자리는 다음과 같은 순서로 채워진다. 비어있는 연속 구간들 중에서 가장 길이가 긴 구간을 고른다. 그리고 그 구간의 중앙에 앉는다. 구간의 길이 L이 짝수일 경우에는 L/2번째 자리에 앉는다. 길이가 가장 긴 구간들이 여러개 있을 경우에는 앞쪽의 구간을 고른다. 이러한 방식으로 자리를 채워나갈 때, Q개의 숫자 $b_i$가 주어진다. 문제에서 원하는 출력은 $b_i$번째에 채워진 자리의 위치이다. 제한은 $ 1 \leq N \leq 10^5 $, $ N \leq M $, $ 1 \leq Q \l..
백준 19589번 카드 셔플 문제 요약 처음에 $a_i = i$인 길이 N짜리 배열 a가 주어진다. 다음 쿼리를 처리하자. x y가 주어지면 [x, y]를 제일 앞으로 옮긴다. x y가 주어지면 [x, y]를 제일 뒤로 옮긴다. x y가 주어지면 [x, y]에 위치한 카드들에 대해서 리플셔플을 한다. N은 최대 100만, 쿼리 수는 최대 20만이다. 3번 쿼리는 구간의 길이가 1000을 넘지 않는다. 풀이 1, 2번은 스플레이트리로 쉽게 가능하다. 3번 쿼리고 [x, y]구간을 잘 모아준다음에 해당 서브트리를 inorder로 탐색해줘서 배열을 만들어준 다음에 잘 섞어준 뒤에 다시 inorder로 탐색하면서 노드의 값들을 바꿔주면 된다. 다행이 3번 쿼리에 들어오는 구간은 길이가 1000이 최대라서 위 방식으로 처리해도 된다. #in..
백준 16586번 Linked List 문제 요약 처음에 $a_i = i$인 배열이 주어진다. 다음과 같은 쿼리를 처리해라. a, b가 주어지면 a를 b의 오른쪽으로 옮기는 것이다. 그리고 a의 이동거리를 출력한다. 모든 쿼리를 처리한 다음에는 전체 배열을 출력해야 한다. 배열의 길이랑 쿼리 수는 최대 10만개다. 풀이 쿼리를 이렇게 생각할 수 있다. a, b가 주어지면 먼저 $a$의 위치를 찾고 $a$를 배열에서 지운다. 그 뒤에 $b$의 위치를 찾고 그 뒤에 $a$를 넣어준다. 이동거리는 빼기 전 $a$위치랑 넣은 후에 $a$위치를 알면 바로 계산할 수 있다. 문제는 이걸 효율적으로 관리할 수 있는 방법이 무엇이냐인데 스플레이트리를 사용하면 빠르게 관리할 수 있다. 배열을 트리로 만들어 줄 때, $i$가 적혀있는 노드의 포인터를 저장해놓는..
백준 17607번 수열과 쿼리 31 문제 요약 0과 1만 있는 길이 N인 배열 A가 주어진다. 다음 쿼리를 처리해라 L R, [L, R]구간을 뒤집어라. L R, [L, R]구간에서 제일 긴 1로만 된 연속 구간의 길이를 출력한다. 풀이 1번 쿼리가 없는 경우에는 금광세그라는 이름으로 유명한 세그트리를 조금만 바꿔서 사용하면 2번 쿼리가 해결 가능하다. 이 세그에 대해서는 여기에 어느정도 설명을 했다. 이제 이걸 스플레이 트리로 옮겨주면 된다. 다만, 주의할 점은 구간을 뒤집었으면 노드들이 관리하는 값이 달라질 수도 있다는 점이다. 뒤집는 쿼리가 들어온 다음엔 루트로 쭉 올라오면서 노드들을 업데이트 해주자. #include using namespace std; using ll = long long; int N, M; int arr[1000..
백준 13543번 수열과 쿼리 2 문제 요약 처음에 길이 N인 배열 A가 주어진다. 이 배열에 대해서 다음 쿼리를 처리해야 한다 p v가 주어지면 $A_p$앞에 v를 추가합니다. p가 주어지면 $A_p$를 제거합니다. p v가 주어지면 $A_p$를 v로 바꿉니다. l r k가 주어지면 $l \le i \le r$에 대해서 $\sum A_i(k-l+1)^k \mod 2^{32}$를 구합니다. N과 쿼리 수는 둘 다 최대 10만입니다. 풀이 1, 2, 3번 쿼리는 스플레이 트리를 이용하면 쉽게 처리가 가능합니다. 4번 쿼리에 집중해보죠 스플레이 트리로 배열을 다룰 때, 하나의 서브트리는 하나의 연속 구간을 나타냅니다. k가 0부터 10까지이므로 서브트리의 루트는 해당 구간에 대해서 모든 k에 대한 답을 가지고 있다고 합시다. 그러면 이런 서..
백준 3444번 Robotic Sort 문제 요약 길이가 N인 배열에 대해서 정렬을 진행한다. 정렬 과정은 다음과 같다. $i$번째 과정에서 배열에서 $i$번째로 작은 원소를 $i$에 위치시키려고 한다. 이를 위해서 매 과정마다 $i$번째로 작은 원소를 $[i, N]$에서 찾고 그 위치를 $p$라고 하면 $[i,p]$를 뒤집어서 정렬을 수행한다. 여기서 숫자가 같더라도 원래 배열에서 더 앞에 있는 것을 작은 것으로 친다. 이 때, 각 과정마다 $i$번째로 작은 원소의 위치인 $p$를 모두 출력하라. N은 최대 10만이다. 풀이 먼저 각 배열의 원소에 대해서 제시한 방법대로 정렬을 했을 때 해당 원소가 어디에 위치하는지를 계산한다. 이는 $O(NlogN)$에 가능하다. 위에서 계산한 값을 $pos_i$라고 하자. 그러면 각 과정에서의 $a_p ..
백준 13159번 배열 문제 요약 처음에 $a_i = i$인 크기가 N인 배열 $a$가 주어진다. 이 배열에 대해서 다음과 같은 쿼리를 수행하고 모든 쿼리를 수행한 뒤에 배열 $a$를 출력한다. 풀이 해당 문제는 스플레이 트리로 해결이 가능하다. 제일 처음에는 선형 모양의 스플레이 트리를 만들고 1부터 N까지를 차례대로 값에 넣어주도록 하자. 1번 쿼리는 각 노드 별로 최솟값, 최댓값, 합을 관리해줌으로 값은 구할 수 있고 구간을 뒤집는 연산은 Lazy Propagation으로 가능하다. 2번 쿼리는 k가 양수인 경우에는 [l,r]을 오른쪽으로 shift해야 되는데 이 경우는 구간을 뒤집는 연산을 세번 하면 가능하다. [r-k+1, r]을 먼저 뒤집고, [l,r-k]를 뒤집고 그 다음엔 [l,r]을 뒤집으면 shift가 완료된..

티스토리툴바