-
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,...
ahgus89's profile imageahgus89
2020-05-20 16:00
-
Dual
두 번째 주의 AlgoShitPo에서 dual of a planar graph를 작성하게 된 ahgus89입니다. 평면 그래프(planar graph) 평면 그래프란, 이름처럼 평면 위에 놓여져 있는 그래프를 의미합니다. 정확히는, 적당한 평면이 존재하여 어떤 두 간선도 정점을 제외하고 교차하지 않는 그래프를 말합니다. 유명한 평면 그래프와, 그렇지 않은 것들의 예시로는 다음과 같은 것들이 있습니다. $K_5$나 $K_{3, 3}$을 minor로 가지는 것과 평면 그래프가 아님이 동치임이 알려져 있습니다.(Wagner’s theorem) 평면 그래프에서 성립하는 유명한 관계식이 몇 가지 있습니다. 단순 연결 평면 그래프가 $v \geq...
ahgus89's profile imageahgus89
2020-03-23 02:25
-
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$를...
ahgus89's profile imageahgus89
2020-02-09 00:00