안녕하세요.. 요즘 알고리즘 공부를 열나게 하고있는 한 학생입니다..

이전부터 항상 의문인 점이 있어서 결국 이렇게 글을 통해 질문을 드립니다.

보통 동적 계획법(다이네믹 프로그래밍) 이라고 하면 흔히들 점화식을 찾아서, table형태의 값을 채워 나가는 방식을 많이들 사용하고 있습니다... 만.

프로그래밍 대회에서 배우는 알고리즘 책에서 처럼 저또한,
전체 탐색 및 메모이제이션 형태의 해답이 사람들이 인지하기 더욱더 직관적이라고 생각합니다. (table형태의 방식은, 구현은 편하나 해당 점화식을 찾는게 너무나 어려운 경우가 많습니다.. 물론 머리가 좋으신분들은 예외..)

그래서 저는 요즘 너무 혼란스럽습니다... ㅎ

Table형태의 동적계획법 으로 풀수 있는 문제는
탐색을 통한 메모이제이션으로 모두 바꿔풀 수 있다.

이 가정이 성립하는지 너무 궁금합니다.

막상 메모이제이션을 통한 답을 찾다보면, 해답을 찾기위해 매우 꼼꼼하게 조건 처리를 한다던가 실수를 유발할 가능성이 높아 보이기도 하고, 또한 Stack 호출 및 메모이제이션을 하기위한 메모리 초기화 등과 같은 부수적인 일들이 늘어나 비효율 적인 것이 아닌가 라는 생각도 듭니다..

너무 궁금합니다. 모든 Table형태로 푸는 동적계획법은
전체탐색을 통한 메모이제이션 방법을 통해 풀수 있는 걸까요..?

여러분들의 생각이 궁금합니다..

감사합니다 ^^ 좋은 하루 되세요 ㅎ