Data Structure, Dynamic Programming
21 Jan 2020 | Data Structure개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)
Dynamic Programming » planning
Recursion에 의해 나오는 다양한 함수호출 결과를 저장, 재활용함으로써 실행시간을 빠르게 하는것

- overlapping sun-instance: F4를 구하기 위해 F2, F1(sub-instance)들이 overlapping하고 있음
어떻게 이루어지는가?
- Setting up recurrence
- Relating a solution if a large instance to solutions of some smaller instances
- Solve small instances once
- Record solutions in s table
- Extract a solution of a larger instance from the table
Memoization
기존의 함수 호출과 결과를 재활용하기 위해 저장하는 것
Memoization과 이전에 Recursion을 돌아가기 위해 만든 Stackframe 사이에는 상반된 철학적 차이가 있다.
- Memoization: 밑에서부터 올라가는 접근. 언제 F4에 접근할 수 있을지는 모르며 과거에 풀어왔던 것을 기록해가며 결과를 도출해나가는 것
- Recursion Stackframe: 위에서부터 아래로 접근. 풀려고 하는 목표를 먼저 실행하고 sub-instance들을 call
접근방법이 완전히 다르다.
Recursion이 overlapping sub-instance가 많다고 하면 Dynamic Programming을 이용해 문제를 풀어
반복되는 동일한 함수호출을 줄인다. 이때 함수결과를 저장할 수 있는 공간이 Memoization table이다.