본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2016 (2)
      • IOI2015 (3)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

Bostan Mori 알고리즘

Bostan Mori 알고리즘은 2020년 8월 Alin Bostan과 Ryuhei Mori가 작성한 이 논문에 소개되어 있는 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 알고리즘이다. Bostan Mori 알고리즘 이외에 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 방법은 이 글을 참고하자. $D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자. $$D_i = \sum_{j=1}^{k}{c_jD_{i-j}} = c_1D_{i-1} + c_2D_{i-2} + \cdots + c_kD_{i-k}$$ 이러한 선형점화식이 주어졌을 때, $D_N$..

공부 2022. 11. 30. 15:53
선형점화식 빠르게 계산하기

$D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자. $$D_i = \sum_{j=1}^{k}{c_jD_{i-j}} = c_1D_{i-1} + c_2D_{i-2} + \cdots + c_kD_{i-k}$$ 이러한 선형점화식을 가지는 가장 유명한 예시는 피보나치 수열이다. 피보나치 수열은 위 식에서 $k=2$, $D_0 = 1$, $D_1 = 1$, $c_1 = 1$, $c_2 = 2$이다. 이러한 선형점화식이 주어졌을 때, $D_N$을 빠르게 구하는 방법을 알아보자. 1) 행렬 곱셈을 이용한 방법 $$\begin{pmatrix} D_N \\ D_{N-1}\\ D_{N..

공부 2022. 11. 30. 10:14
다항식 나눗셈의 몫을 빠르게 구하는 방법

차수가 $n$인 다항식 $f(x) = c_0 + c_1x^1 + c_2x^2 + \cdots + c_nx^n (c_n \ne 0)$가 있다. 그리고 차수 $m$인 다항식 $g(x) = d_0 + d_1x^1 + d_2x^2 + \cdots + d_mx^m (d_m \ne 0)$이 있다. 이를 다항식 $q$와 $r$을 이용하여, $f(x) = g(x)q(x) + r(x)$라고 나타내 보자. $r(x)$의 차수가 $m$보다 작은 경우, $f$를 $g$로 나눈 몫을 $q$, 나머지를 $r$이라고 정의한다. 다항식 $q$의 차수는 $n-m$이다. 다항식의 나눗셈을 교과과정에서 배운대로 구현한다면 $O(nm)$ 시간복잡도가 된다. 이를 좀 더 빠르게 하는 방법에 대해서 알아보자. $\textrm{Rev}(f)$를..

공부 2022. 11. 29. 23:09
이전 1 2 3 4 ··· 47 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • shortcut 만점 코드의 반례가 존재하는 것 같습니⋯
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
Total
257,040
Today
43
Yesterday
52
링크
TAG
  • BOI 2009
  • z-trening
  • moore
  • Greedy Method
  • Algorithm
  • IOI2014
  • HackerRank
  • majority
  • dynamic programming
  • Boyer-Moore Majority Vote Algorithm
  • Segment tree
  • Splay Tree
  • IOI2013
  • Dijkstra
  • TRIE
  • ioi
  • BOI
  • BOI 2001
  • IOI2011
  • Tree
  • Divide & Conquer
  • Dynamic Pramming
  • Boyer
  • optimization
  • USACO
  • Parametric Search
  • IOI2012
  • Knuth Optimization
  • idea
  • vote
more
«   2023/03   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
  • 2022/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바