QCW-Yaho - talALGO

talALGO

Sign in Subscribe

QCW-Yaho

Radix Sort

오랜만에 나는 야호다. 오늘은 라딕스 소트라는걸 배워보자. 본인은 매우 애용한다. Counting Sort Radix Sort를 배우기 전에 우리는 Counting Sort에 대해 알아보아야 한다. 만약 다음과 같은 문제가 주어졌다고 하자. 1000만 개의 숫자가 주어진다. 각 숫자는 0 또는 1이다. 이를 정렬하라. 비교기반 정렬을 때리면, $$O(nlogn)$$으로 매우 오랜시간이 걸린다. 하지만 우리는

Splay Tree

나는 야호다. 오늘은 Splay Tree에 대해 설명하겠다. Splay Tree는 무엇인가 Splay Tree는 균형이진탐색트리(Balanced Binary Search Tree, BBST)의 한종류이다. Splay Tree라는 이름이 붙은 건 Splay라는 재밌고도 신기한 연산을 사용하여 amortized $$O(log n)$$의 시간복잡도를 유지하기 때문이다. 설명에 앞서 균형이진탐색트리에 대해 잠깐 알아보고 가자. 이진탐색트리는 특정 데이터의 삽입, 삭제,

키타마사 법

나는 야호다. 오늘은 키타마사법에 대해 배워보도록 하겠다. 선형점화식을 풀자 PS를 하다보면 점화식을 풀 일이 종종 생긴다. 그 중에서 가장 많이 나오는 점화식은 당연히 다음과 같은 선형점화식의 꼴일 것이다. $$ \begin{aligned} a_n&=c_1 a_{n-1}+c_2 a_{n-2}+... +c_m a_{n-m}\\ &=\sum c_i a_{n-i} \end{

Fast Fourier Transformation

Fast Fourier Transformation

나는 야호다. 오늘은 FFT에 대해 알아보겠다. 이의 이론적 배경을 위해서는 선형대수학에 대한 지식이 다소 필요할수 있으므로 알아서 잘 알아듣길 바란다. (설명은 할것이니 걱정안해도된다.) 선형대수학 기본 본인이 선형대수학에 자신이 있다면 이 부분은 과감히 넘겨도 좋다. 벡터에 대해서 들어본 적이 있는가? 보통 벡터라고 하면 떠올리는 게 고등학교 기하와 벡터에서 배우는 그 벡터일것이다.

Chinese Remainder Theorem

Chinese Remainder Theorem

나는 야호다. 오늘은 중국인의 나머지정리에 대해 배워보자. $$ \begin{aligned} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ ...\\ x &\equiv a_n \pmod {m_n} \end{aligned} $$ 이런 문제를 푸는데 유용한 방법인 것이다. 중국인의 나머지 정리는 다음과 같다. $$m_i$$가 모두 쌍마다 서로소라면, 위의

BOJ 5916 농장관리

나는 야호다. 오늘은 농장관리라는 문제를 풀어볼거다. 문제: https://www.acmicpc.net/problem/5916 문제는 HLD의 기본문제다. HLD의 설명은 /hld 를 봐라. HLD의 기본만 알고있다면, 약간 까다로운 점이 존재하는데, 바로 이 문제의 쿼리가 노드에 있는게 아니라, 간선에 있다는 점이다. 간선 쿼리의 경우에는 그 간선이 자식쪽에 해당하는 노드에 속해있다고 생각하면 된다. 따라서

Codeforces Global Round 5 후기

나는 야호다. 버추얼하나 까서 요약남김 A. Balanced Rating Changes 제로 섬인 배열이 주어졌을때 이를 각각 /2를 하는데, 짝수의 경우는 그냥 /2를 하면되고 홀수의 경우 floor(a/2)와 ceiling(a/2)를 번갈아 하면 된다. O(n) B. Balanced Tunnel Ai를 처음에 i번째로 들어온 자동차가 터널을 통과한 등수라고 하자. A1~

Extended Euclidean Algorithm

Extended Euclidean Algorithm

gcd부터 canon_egcd까지