-
Linear Recurrence
이번 글에서는 선형 점화식의 $n$번째 항을 빠르게 구하는 방법에 대해 알아보도록 하겠습니다. 문제 다음과 같이 정의되는 무한수열 ${a_n}$이 있습니다. \[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\] $n$과 초항 $a_1, a_2, \ldots, a_k$, 계수 $c_1, c_2, \ldots, c_k$ 이 주어지면 $a_n$을 구하는 것이 목표입니다. 가장 간단한 방법부터, 이번 글의 최종 목표인 $O(k log k log n)$ 만에 구하는 방법까지 알아보도록 하겠습니다. 정의를 대입 가장 간단한 방법으로, 점화식 그대로 $a_{k+1}, a_{k+2}, \ldots,...
-
번사이드 보조 정리
첫 번째 주의 AlgoShitPo에서 ahgus89의 지목을 받아 Burnside’s Lemma를 작성하게 된 justiceHui입니다. 서론 번사이드 보조 정리는 원순열 등의 경우의 수를 구하는 문제에서 자주 나오는 정리입니다. 공부하기 위해 책을 보거나 검색을 하면, $\displaystyle \frac {1}{n}\sum_{k=1}^{n} c(k)$같은 공식만 나와있거나 Group Theory가 튀어나오는 경우가 대부분입니다. 저는 고등학교에 재학중인 학생으로써, 고등학교 수준에 맞춰 번사이드 보조 정리의 아이디어를 소개하는 것에 초점을 맞추도록 하겠습니다. 문제 1 위 그림처럼 구슬 4개로 구성된 목걸이가 있을 때, 각 구슬을 빨간색 혹은 파란색으로 색칠하는 경우의...
-
Simplex
첫 번째 주의 AlgoShitPo에서 Ryute의 지목을 받아 Simplex Method를 작성하게 된 ahgus89입니다. 서론 Simplex Method는 Linear Programming(LP) 문제를 해결하는 방법 중 하나입니다. LP는 무엇일까요? 위키백과에 따르면, “주어진 선형 조건을 만족시키면서 선형인 목적 함수를 최적화하는 문제” 라고 합니다. 중학교 때 배운 부등식의 영역 문제를 생각해봅시다. 다음과 같은 문제가 있습니다. 물건 $P$, $Q$를 만들 예정인데, 재료 $A$, $B$가 각각 $100g$씩 있습니다. $P$ $1g$를 만들 때는 $A$를 $1g$, $B$를 $2g$ 사용하며, $Q$ $1g$를 만들 때는 $A$를 $3g$, $B$를...