이진 트리는 일반적인 트리에 비해 효율/구현에서 많은 이점을 갖고 있습니다. 자식의 개수가 2개 이하로 일정하고, 트리의 순회 순서를 강제하기 쉬우며, 모든 정점의 차수가 3 이하라는 성질을 갖고 있는 이진 트리는 일반적인 트리에서는 적용하기 어려운 다양한 알고리즘을 적용할 수 있게 해줍니다.
놀랍게도 모든 트리는 이진 트리로 변환할 수 있습니다. 이 글에서는 주어진 트리의 조상-자손 관계, 그리고 정점 간의 거리를 유지하면서 선형 시간에 이진 트리로 변환하는 방법을 다룹니다.
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년짜리 뒷북입니다.