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

PS 이야기

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

PS 이야기

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

dynamic programming (2)
Divide & Conquer Optimization

Divide & Conquer Optimization은 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 주로 Dynamic Programming에서 쓰인다고 생각할 수 있으나, Dynamic Programming이 아닌 상황에서도 널리 쓰일 수 있다. 조건 1) DP 점화식 꼴 $D[t][i] = \min_{k < i}(D[t-1][k] + C[k][i])$ 조건 2) $A[t][i]$는 $D[t][i]$를 만족시키는 최소 $k$라 할 때 아래 부등식을 만족 $A[t][i] \leq A[t][i+1]$ 위 두 조건을 만족하면 원래 $O(KN^2)$의 시간복잡도를 갖는 DP를 Divide & Conquer를 통해 $O(KN \lg N)$에 해결 할 수 있다. 여기서 $K$는 단계 수(가능한 $t$..

공부 2016. 6. 23. 16:31
Knuth Optimization - Dynamic Programming

Knuth Optimization은 Dynamic Programming에서 점화식이 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 조건 1) DP 점화식 꼴 $D[i][j] = \min_{i < k < j}(D[i][k] + D[k][j]) + C[i][j]$ 조건 2) Quadrangle Inequalty (사각부등식) $C[a][c] + C[b][d] \leq C[a][d] + C[b][c], a \leq b \leq c \leq d$ 조건 3) Monotonicity (단조성) $C[b][c] \leq C[a][d], a \leq b \leq c \leq d$ 조건 2와 조건 3을 만족하면 $A[i][j]$ = $D[i][j]$가 최소가 되기 위한 가장 작은 $k$라고 했을 때 아래 식을..

공부 2016. 6. 23. 15:03
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Google CodeJam 2019 Round..
  • Stern-Brocot 트리
  • IOI 2018 Day 2 문제 및 해법
  • IOI 2018 Day 1 문제 및 해법
최근에 달린 댓글
  • 이게 바로 빌라봉에서 봤던 그..
  • 팬이에요!
  • fft코드 질문입니다. a와 b의..
  • H번 그래프에서 member1에서 p..
Total
158,303
Today
96
Yesterday
87
링크
TAG
  • optimization
  • BOI 2009
  • Segment tree
  • Greedy Method
  • idea
  • Parametric Search
  • Dijkstra
  • IOI2011
  • TRIE
  • ioi
  • vote
  • IOI2012
  • Tree
  • HackerRank
  • Boyer
  • USACO
  • moore
  • majority
  • IOI2013
  • z-trening
  • Algorithm
  • Boyer-Moore Majority Vote Algorithm
  • IOI2014
  • BOI
  • Dynamic Pramming
  • Divide & Conquer
  • dynamic programming
  • Splay Tree
  • BOI 2001
  • Knuth Optimization
more
«   2019/12   »
일 월 화 수 목 금 토
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        
글 보관함
  • 2019/05 (2)
  • 2018/09 (2)
  • 2018/05 (2)
  • 2017/11 (1)
  • 2017/08 (3)

Blog is powered by Tistory / Designed by Tistory