Joonas' Note

문제링크: https://www.acmicpc.net/problem/9373복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다.복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반..

문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php 정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..문제수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q <= 200,000이다.Q개 줄의 입력이 주어지는 데, 입력이 0 a b 형태면 a번째 숫자를 b로 바꾸고, 1 이면 연속된 숫자들의 최대 합을 출력한다. 전형적인 세..

Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다. 트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다. 균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( ..

확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다.\(as + bt = gcd(a,b)\)을 만족하는 정수 \(s\), \(t\) 짝을 찾아낼 수 있다.증명은 생략하고 어떻게 사용하는가를 적어볼까 한다.초기 조건\(s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b\)진행$$ \begin{align} q_i \le..