2018 NYPC에서 우승하신 yclock님께서 상금으로 받은 500만원의 10%를 기부하셨다는 소식을 들은 적이 있습니다. 브랜디 대회 상금 규모가 매우 크다는 것을 알고, 참가 신청을 하면서 “100만원 이상 받으면 상금의 10%를 기부하겠다”고 선언했습니다. 결국 1000만원을 받았고, 100만원을 후원하기로 했습니다.
저부터 기부를 하면 나중에는 좋은 문화가 형성되지 않을까요? 많은 사람들이 기부를 했으면 하는 마음에서 이 글을 작성합니다.
키타마사법(Kitamasa Method, きたまさ法)은 $A_N = c_1A_{N-1} + c_2A_{N-2} + \cdots + c_KA_{N-K} = \sum_{i=1}^{K} c_iA_{N-i}$와 같은 선형 점화식의 $N$번째 항을 $O(K^2 \log N)$, 더 나아가 $O(K \log K \log N)$에 계산하는 알고리즘입니다.
이 글에서는 키타마사법을 최대한 쉽게 설명하는 것에 초점을 두기 때문에 엄밀한 증명이 생략될 수 있습니다. 양해 부탁드립니다.
※ 1년짜리 뒷북입니다.