dp문제 바텀업일지 탑다운일지 쉽게 구분할방법없나

[익명(218.38)]

걍 양치기 뿐인가?

바텀업으로 ㅈㄴ 풀다가 계속 에러터저서 빡쳐서 다른애들꺼보니까 탑다운으로 ㅈㄴ 쉽게 해놨네 ㅅㅂ

[익명(175.196)]

문제마다 다름

[익명(218.38)]

유형암기밖에없나 ㅅㅂ

[익명(175.196)]

ㄴㄴ 새로운 유형이 계속 나오는데 암기를 어케함. 걍 많이 풀어보고 감 잡아아지.

[익명(222.111)]

탑다운은 필요할 때 구하고, 바텀업은 그런 거 없다고 일다 다 구해놓음. 그럼 탑다운이 무조건 유리한 거 아니냐 할 수 있는데 어차피 다 구해야 된다는 것을 알 때는 똑같이 다 구한다 해도 바텀업이 더 빠름. 1 탑다운은 재귀 쓰는 경우가 많고, 바텀업은 보통 루프로 도는데, 재귀가 훨씬 비용이 큼. 2 바텀업은 정확히 한번만 구하는데, 탑다운 계산 자체는 한번 하지만, 계산 했는지 안 했는지는 여러번 조회하기 때문에, 추가 비용이 발생함

[익명(222.111)]

좀 더 비교하면, 탑다운이 구현하기 더 쉬울 때가 많음. 재귀가 사람의 일반적인 사고와 더 친숙한 듯. 그래서 접근 순서가, 1. 아 이거 모든 하위 문제를 다 풀어야 될 것 같다? 그럼 바텀업 도전 2. 근데 점화식 표현하기 너무 어렵다? 그냥 탑다운 도전 3. 탑다운으로는 너무 느리네? 혹은 메모리 터진다?(재귀 함수) 어쩔 수 없이 바텀업... 근데 3번이 실제로 발생하는지 기억 안 남....

[c언어입학(112.153)]

3번의 경우는 그냥 무조건 최소 거리임.. 최소 거리는 안 터져 동시에 탐색시키면서 젤 짧은 경로가 발견되면 바로 종료하면 되는데, 탑 다운은 최소 경로 문제에서 무조건 모든 경로를 탐색해야됨.. dp로 반복되는 경로를 조금 줄일 수 있을 뿐..

[c언어입학(112.153)]

최대 거리를 구하라. 최소 구간의 합을 구하라 최대 구간의 합을 구하라. 이 3문제 류는 일단 최대 거리를 구한다는건 다 경로를 탐색해야만 알 수 있음.. 그래서 dp+dfs가 이득. 최소 구간의 합.. 역시 모든 경로에서 구간의 합을 알아야 알 수 있음 dp+dfs가 이득.. 최대 구간의 합 역시 마찬가지.. 위 같은 문제는 탑다운이 빠름

[c언어입학(112.153)]

혹시 몰라 덧 붙이자면 최소 구간의 합 역시 dp+dfs가 빠른 이유는 당연하지만, 적은 것만 탐색한다고 빠른게 아님 예를 들어, 왼쪽에 작은 거 있고, 오른 쪽에 살짝 큰게 있으면, 왼쪽거로 가다가, 오른쪽까지 도달해야되면, 어쩔수 없이 다른 위치의 오른쪽 더해야되서, 경로 자체는 더 많이 더 해야되서, 그냥 오른쪽 더할 때 보다 많은 값이 나올 가능성이 있음.. 그래서 dp+dfs가 빠름

[익명(222.111)]

허허... 정성스런 답글 고맙습니다, 근데 제가 사실 요즘에는 문제 잘 안 풀어서 정확히 이해는 못하겠네요...그냥 기억을 더듬으며 쓴 댓글이라 제가 위에 쓴 것도 아마 틀린 부분이 많을 수 있겠네요. 다른 사람들이라도 도움 받을 수 있게 틀린 부분들 보충 설명 해줘서 고맙습니다.