Contents
3.1.2. ¶
- sort/
- subsequence/ - , , . 하 ..
3.13.1. ¶
- 태
- _1C: 857
- Consonants, Pogo, The Great Wall
- Consonants, Pogo, The Great Wall
- _1C: 857
def Solve(x, y): N = 0 sum = 0 while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1: N += 1 sum += N result = "" while N > 0: if abs(x) > abs(y): if x > 0: result += 'E' x -= N else: result += 'W' x += N else: if y > 0: result += 'N' y -= N else: result += 'S' y += N N -= 1 return result.reversed()
- 학
3.14. 6 27 ¶
- 태 : Dynamic Programming 6.1~6.3
- Shortest Path : DAG(directed acyclic graphs) Source dist(v) = min{dist(v) + l(u,v)}
- 170p
- 170p
- Longest increasing subsequence : DAG .(increasing하 edge) 하 L(j) = 1+ max{L(i) : (i,j)}행
- path 한 택 path 할 .
- path 한 택 path 할 .
- Edit distance : 하 (exponential polynomial 6.)
- Similar to DTW
- Similar to DTW
- Shortest Path : DAG(directed acyclic graphs) Source dist(v) = min{dist(v) + l(u,v)}
- : 3
- 학 : Hoffman code - ..
3.15.2. ¶
- 태 : DP
- Maximum Sum - kadane's algorithm
- proof - http://prezi.com/fsaynn-iexse/kadanes-algorithm/
- Array subset 합 크 하 .
- proof - http://prezi.com/fsaynn-iexse/kadanes-algorithm/
- :
- Topological sort -
- Strongly Connected Component(SCC)
- Tarjan's strongly connected components algorithm - 크
- URL ' .
- URL ' .
- Tarjan's strongly connected components algorithm - 크
- Topological sort -
- 학 :
3.16.2. ¶
- 태 : Dynamic Programming
- KnapsackProblem/태 : 0/1 해했..
- KnapsackProblem/태 : 0/1 해했..
- 학 : 한?
- : ?
3.17.2. ¶
- prime_path http://211.229.66.5/30stair/prime_path/prime_path.php?pname=prime_path
- 학: - ,
- 태: gusul/태
3.18. 7 25 ¶
- () - http://ko.wikipedia.org/wiki/
- !n = (n - 1) * (!(n - 2) + !(n - 1))
- - http://blog.naver.com/PostView.nhn?blogId=kcg2271&logNo=90064644595
- !n = (n - 1) * (!(n - 2) + !(n - 1))
- DP worm/태 - 화 k=0 k=1, k=2 히 하. - 하 편함.
- Bar_code - http://211.229.66.5/30stair/bar_code/bar_code.php?pname=bar_code
- - 테 한 DP, d(bar,unit,width) bar bar 하, unit bar 폭 width . 한 하 d(bar,unit,0 ~ width) 해 .
- 화 : d(bar, unit, width) += d(bar - 1,unit - width,l);
- 화 하 했, index 힘.
- 하 1110110 , 1110110 110 하 , 10 하 . 1110110 111000 하 , 11100 하 . dp테 해 한 해 , 해 index 할 .
- 할 : dp테 ( ) 한 해 한. 튜 할 , 테 하 힘..
- - 테 한 DP, d(bar,unit,width) bar bar 하, unit bar 폭 width . 한 하 d(bar,unit,0 ~ width) 해 .
3.21. 8 13,8 15 ¶
- 2012 ICPC : 크
- C - Critical 3-path
- , critical path 해 - 해 Fundamental of DataStructure 하.
- , critical path 해 - 해 Fundamental of DataStructure 하.
- C - Critical 3-path
- 폴
- DP. 태 POLY/태
- DP. 태 POLY/태
3.22. 8 21,8 28, 8 30 ¶
- 2회 학 회 합 크
- 형 2 판하
Ax1 A형 x표. By2 B형 y표 if Ax1 < Bx1 if Bx1 > Ax2 && By1 > Ay2 if By2 > Ay1 then else else else A B
- Sliding Window Minimum Algorithm - http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html