Berlekamp-Massey 알고리즘은 내가 가장 좋아하는 알고리즘 중 하나이다. 지금까지 이 알고리즘을 블랙박스 형태로 내부 동작을 모르는 채 사용했지만 이번 기회에 한 번 알아보는 것도 좋을 것 같아서 찾아보게 되었다. (몰라도 쓰는데 문제는 없다.) Shift-Register Synthesis and BCH Decoding 이라는 1969년에 나온 오래되고 클래식한 논문에 있는 알고리즘이었다. 정말 정말 좋은 리소스가 있어서 쉽게 접할 수 있었다. 엄밀한 증명은 하지 않고 어떻게 동작하는지만 남긴다. 선형 점화식DP에도 많이 나오는 선형 점화식은 1차원 수열상에서 이전 몇 개의 항들의 선형 결합을 통해 다음 항을 만드는 수열이 된다.$a_{i} = \displaystyle\sum_{j=1}^n c..
