자연어 처리에서 동적계획법이 참 많이 쓰이는것 같다

[asdf(98.212)]

뭐 확률 모델 기반이라서 그런거겠지만...

[d(58.239)]

dynamic programming 몰라?

[d(58.239)]

top-down approach랑 bottom-up approach가 있는데

[d(58.239)]

recursion으로 해를 구하다 보면 문제 영역을 중복해서 탐색하는 경우가 아주 많음. 그런데 단순히 중복 계산만 제거해도 time complexity가 exponential에서 polynomial로 떨어질 수 있기 때문에, recursion에서 한번 계산한 부분해를 cache에 저장하고 중복 계산하지 않도록 하는 기법이 top-down dynamic programming이고

[d(58.239)]

반대로 지금까지 계산한 부분해를 이용해서 새로운 부분해를 구축하는 식으로 점점 해의 사이즈를 키워서 원하는 크기에 도달하도록 하는 방법이 bottom-up dynamic programming인데, 일반적으로 dynamic programming이라고 하면 bottom-up만을 말하는 경우가 많음

[d(58.239)]

https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

[d(58.239)]

알고리즘쪽 이론임. 알고리즘 수업 들었으면 내용은 알텐데