[일반] 그리디 dp 차이가 이거 맞아?

[익명(119.193)]

그리디는 매 상황마다 무조건 베스트 고르다보면 결국 종착점에서의 베스트가 그 베스트가 되는거고

dp는 매 상황마다 여러 개의 케이스에서 각각의 베스트 고르다보면 결국 종착점에서 나온 여러 개의 케이스에서 베스트 고르는게 베스트인건가?

둘 다 공통점은 sub-problem의 베스트가 그 다음 sub-problem으로 이동한다는거?

[익명(14.40)]

dp는 베스트를 고른다기 보다는 현 상황에 영향을 주는 작은 상황들을 메모리에 저장해서 쓰는거 아닌가

[익명(211.57)]

Dp는 결국 모든 경우의 수를 다 보는거고 그리디는 그냥 부분부분만 계속 보는거임

[익명(211.36)]

난 완탐이 진화한게 dp나 백트래킹이라고 생각하고있음.. - dc App

[익명(14.32)]

그냥 순수하게 memoization 쓰면 다 dp다 라고 하면 되는 거 아닌가

[익명(14.32)]

dp 중에서도 플로이드 워셜 같은 거는 dp인데 그리디 느낌이 나긴 하지

[익명(49.167)]

어느 부분에서 그게 그리디 느낌이 남?

[익명(14.32)]

걍 점화식에 min, max 들어가는 dp는 내 관점에서 그리디의 느낌이 남

[익명(61.74)]

플로이드워셜은 내관점에서 네트워크플로우느낌남

[익명(221.141)]

dp는 완전탐색을 효율적으로 하는거임