2025
알고리즘 어떻게 빠르게 할 수 있을까? $feat.$ 피보나치
저명한 수학자 가우스는 10살 무렵 학교에서 1부터 100까지 더하라는 문제를 받았고, 또래 아이들이 1부터 하나씩 더해갈 때 가우스는 특정한 위치의 숫자들의 합이 101로 일정하다는 것을 알았고 ${(1, 100), (2, 99) …}$ 이들의 개수를 곱함으로써 빠르게 1부터 100까지의 합을 구했습니다. 이런 아이디어는 등차 수열의 합 공식 \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)의 초석이 됩니다. 이 이야기를 떠올리며, 컴퓨터 알고리즘에도 이런 아이디어를 적용할 수 있지 않을까? 하는 호기심이 이 포스트의 출발점입니다.