Problem Solving/알고리즘 강의 (4) 썸네일형 리스트형 Splay Tree와 amortized 시간복잡도 본 글은 이 자료의 전반부를 포스트로 옮긴 것입니다. 독자가 Binary Search Tree와 알고리즘의 연산 시간을 계산하는 법을 안다고 가정하고 글을 작성합니다. Self-Balancing Binary Search Tree(BBST) 이진 검색 트리는 각 노드마다 key를 가지고 있으며 어떤 노드 x의 left children에는 x의 key보다 작은 key를 가지고 있는 노드들이 존재하며, right children에는 x의 key보다 큰 key를 가지고 있는 노드들이 존재하도록 구성한 이진트리입니다. 따라서 이 자료구조는 inorder로 탐색을 진행했을 때, 그 순서가 노드들의 key값을 정렬한 순서와 동일합니다. 그리고 이 순서를 유지하도록 하면서 노드의 삽입, 읽기, 갱신, 삭제(CRUD)를.. 중국인의 나머지 정리 설명(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$가 주어졌을 때.. 이전 1 다음
