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

PS 이야기

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

PS 이야기

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

Knuth Optimization (1)
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 ..

공부 2016.06.23 15:03
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • 2017년 대학생 프로그래밍..
  • IOI 2017 결과 및 총평
  • IOI 2017 Day 2 문제 및 해법
  • IOI 2017 Day 1 문제 및 해법
최근에 달린 댓글
  • 고등부 3번 문제에서 29~48번..
  • 아, 이해 했습니다. 풀이 감사..
  • 이 풀이의 증명을 모르겠습니..
  • 와...대단하셔요 예선문제도..
Total
94,858
Today
11
Yesterday
87
링크
TAG
  • Boyer-Moore Majority Vote Algorithm
  • Parametric Search
  • Dynamic Pramming
  • USACO
  • IOI2014
  • Divide & Conquer
  • z-trening
  • IOI2011
  • Tree
  • HackerRank
  • majority
  • BOI 2001
  • ioi
  • optimization
  • Boyer
  • idea
  • vote
  • TRIE
  • Splay Tree
  • moore
  • Greedy Method
  • IOI2013
  • Knuth Optimization
  • Algorithm
  • BOI
  • Segment tree
  • Dijkstra
  • dynamic programming
  • IOI2012
  • BOI 2009
more
«   2018/04   »
일 월 화 수 목 금 토
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          
글 보관함
  • 2017/11 (1)
  • 2017/08 (3)
  • 2017/07 (2)
  • 2016/11 (1)
  • 2016/10 (2)

Blog is powered by Tistory / Designed by Tistory
  • 페이스북 공유하기
  • 카카오톡 공유하기
  • 카카오스토리 공유하기
  • 트위터 공유하기