셔플의 주기가 O(n)인 이유에 대한 증명입니다.
매번 유도하기 싫어서 적어두는 펜윅 트리 구현 노트
DFT의 개념, DFT를 빠르게 계산하는 데에 쓰이는 FFT와 그 비재귀 구현, DIT/DIF의 차이와 NTT까지 정리했습니다.
스포일러 주의! AtCoder Beginner Contest 335 풀이 및 후기입니다.
배열에서 원소를 2개 제거하여 남은 배열에서 가장 큰 원소가 나머지의 합과 같게 만들 수 있는 경우의 수를 구하는 문제
세 직선 각각에 많은 점이 놓였을 때, 두 직선에 각각 놓인 두 점의 중점이 나머지 한 직선 위의 점인 경우의 수를 구하는 문제
길이 k의 선형 점화식을 따르는 수열의 n번째 항을 O(k logk logn) 안에 구하는 데에는 FFT 나눗셈이 필요 없습니다.
공간에 떠 있는 두 삼각형이 서로 얽혀 있는지 분리되어 있는지 판단하는 문제
애드혹과 케웍을 통한 선분 교차는 머리만 아픕니다. 벡터를 사용해서 분류해야 하는 케이스를 단 2개로 최소화하고 논리적으로 두 선분의 교점을 구해봅시다.
KMP 짜다가 자꾸 off-by-one 에러가 나서 formal하게 알고리즘을 기술해봤습니다. 제가 헷갈려서 썼습니다.
