본문 바로가기

분류 전체보기

 (133)
중국인의 나머지 정리 설명(Chinese Remainder Therem, CRT) 중국인의 나머지 정리(Chinese Remainder Theorem) 2020.04.23 코드가 잘못된 것을 확인했습니다. 앳코더 라이브러리판 crt는 맞는데 제 꺼는 틀렸습니다. 확인하고 수정하겠습니다. 2020.04.27 제가 착각했습니다. 틀린 줄 알았는데 제가 코드를 옮길 때 정확히 옮기지 않았네요. 블로그 상에 올라와 있는 코드는 전부 int인데 long long으로 옮기다가 잘못 옮겼습니다. 포스트의 코드도 long long 버전으로 바꾸겠습니다. $$ \begin{aligned} x \equiv &a_1 \; (mod \; m_1) \\ x \equiv &a_2 \; (mod \; m_2) \\ &\vdots \\ x \equiv &a_k \; (mod \; m_k) \end{aligned}..
모듈러 역원 설명(Modular Inverse) 이 글은 확장 유클리드 알고리즘을 안다는 전제 하에 작성했습니다. 확장 유클리드 알고리즘은 여기에 설명했습니다. 나머지 연산 나머지 연산이란 정수끼리 연산을 할 때, 그 결과로 항상 어떤 수 $N$에 대하여 나머지를 취하는 연산을 말한다. 모듈러 연산이라고도 하며 나머지 연산 상에서 같다는 것을 표기할 때는 작대기 세개짜리 등호를 쓴다($\equiv$) . 어찌 됐든 이 모듈러 연산을 할 때, 덧셈과 곱셈, 뺄셈은 일반적인 정수의 사칙연산과 별 차이가 없다. 하지만 나눗셈의 경우 일단 원래 하던 방식으로 가능한지부터 의문이 든다. 모듈러 나눗셈을 하기 위해서는 역원이라는 개념을 알아야 한다. 어떤 수로 모듈러 나눗셈을 하고자 할 때, 그 수의 곱셈에 대한 역원을 찾고 그 역원을 곱해주는 것으로 나눗셈을 ..
확장 유클리드 알고리즘 설명 이 포스트는 독자가 두 정수의 최대공약수를 구하는 유클리드를 알고 있다는 가정하에 쓰여졌습니다. 베주 항등식(Bezout's Identity) 먼저, 확장 유클리드 알고리즘을 이해하기 위해서는 베주 항등식이 무엇인지 정리하고 머리에 넣어둘 필요가 있다. 다음과 같은 식을 생각하자. $$ ax+by=c \; (a,b는 정수) $$ 위 식이 정수해 $(x,y)$를 가지기 위해서는 $c$가 $GCD(a,b)$의 정수배여야만 한다는 것이 베주 항등식의 내용이다. 이는 확장 유클리드 알고리즘을 사용하게 되는 여러가지 곳에서 자주 나오게 되는 내용이니 기억해둘 필요가 있다. 증명은 사실 나도 안봤다. 확장 유클리드 알고리즘(Extended Euclid Algorithm) 유클리드 알고리즘은 $a,b$가 주어졌을 때..
백준 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에 대한 답을 가지고 있다고 합시다. 그러면 이런 서..

티스토리툴바