학교에서 알고리즘 수업을 듣는데 다이나믹 프로그래밍에는 "Bottom-up"과 "Up-Bottom"
두가지 방식이 있다는 것을 알게 되었습니다.
전자는 보통 배열과 반복문, 점화식을 사용해서 모든 부분문제를 해결하면서 답을 구하는 것이고
후자는 재귀호출 중 이미 계산된 값을 저장하는 배열을 이용해서 문제를 푸는 것이라고 이해했습니다.
그런데 수업 중 후자의 방법이 함수를 호출하는 과정이 반복되기 때문에 전자에 비해 느릴수도 있지만
특정 경우에는 후자의 방법이 더 좋아진다는 설명을 들었습니다.
간략히 설명하시기로는 모든 부분문제를 풀지 않아도 해를 구할 수 있는 문제가 있고 그 경우에는
"Up-Bottom" 방식이 더 효과적일 수도 있다는데 혹시 어떤 문제가 그런 유형에 속하는지 알 수 있을까요?
0-1 배낭 문제에서 배낭 용량은 큰데 아이템은 몇 개 없는 경우가 있겠네요
https://www.acmicpc.net/problem/11669
좋은 예시입니다.
아 두분 모두 감사합니다. ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
hokma 7년 전
학교에서 알고리즘 수업을 듣는데 다이나믹 프로그래밍에는 "Bottom-up"과 "Up-Bottom"
두가지 방식이 있다는 것을 알게 되었습니다.
전자는 보통 배열과 반복문, 점화식을 사용해서 모든 부분문제를 해결하면서 답을 구하는 것이고
후자는 재귀호출 중 이미 계산된 값을 저장하는 배열을 이용해서 문제를 푸는 것이라고 이해했습니다.
그런데 수업 중 후자의 방법이 함수를 호출하는 과정이 반복되기 때문에 전자에 비해 느릴수도 있지만
특정 경우에는 후자의 방법이 더 좋아진다는 설명을 들었습니다.
간략히 설명하시기로는 모든 부분문제를 풀지 않아도 해를 구할 수 있는 문제가 있고 그 경우에는
"Up-Bottom" 방식이 더 효과적일 수도 있다는데 혹시 어떤 문제가 그런 유형에 속하는지 알 수 있을까요?