hokma   1달 전

학교에서 알고리즘 수업을 듣는데 다이나믹 프로그래밍에는 "Bottom-up"과 "Up-Bottom"

두가지 방식이 있다는 것을 알게 되었습니다.


전자는 보통 배열과 반복문, 점화식을 사용해서 모든 부분문제를 해결하면서 답을 구하는 것이고

후자는 재귀호출 중 이미 계산된 값을 저장하는 배열을 이용해서 문제를 푸는 것이라고 이해했습니다.


그런데 수업 중 후자의 방법이 함수를 호출하는 과정이 반복되기 때문에 전자에 비해 느릴수도 있지만

특정 경우에는 후자의 방법이 더 좋아진다는 설명을 들었습니다.


간략히 설명하시기로는 모든 부분문제를 풀지 않아도 해를 구할 수 있는 문제가 있고 그 경우에는

"Up-Bottom" 방식이 더 효과적일 수도 있다는데 혹시 어떤 문제가 그런 유형에 속하는지 알 수 있을까요?

codeonwort   1달 전

0-1 배낭 문제에서 배낭 용량은 큰데 아이템은 몇 개 없는 경우가 있겠네요

hokma   1달 전

아 두분 모두 감사합니다. ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.