[질문] 질문) DP는 보텀업이나 탑다운 둘 중 하나가 되면 반대도 됨?

[울댕별(mypuppystarpoo)]

보텀업으로 구현할 수 있는 문제는

무조건 탑다운으로도 가능한것임?

탑다운은 짜기 쉬운데

보텀업은 아이디어 내기가 넘 어려워서

- dc official App

[익명(112.186)]

봇 -> 탑은 되는데 탑 -> 봇은 안되는 경우 있을걸?

[울댕별(mypuppystarpoo)]

난 무지성 탑빠니까 문제없겠군

[익명(112.169)]

바텁업은 반복계산은 안 하는데 쓸데 없는 거 계산 하는 경우는 있어서 파이썬 같은 경우엔 탑다운은 되는데 바텀업은 tle 걸리는 경우 본 거 같음. 근데 사실 이런 건 제한 조건이 잘못된 거고 의도한 tle는 아닌데 cpp 기준으로 시간제한 걸어두고 파이썬 이면 일괄 몇배 이런 식으로 제한줬을 떄 가끔 나오는...의도치 않은 거라고 봐야지. 여튼 파이썬은 정해로도 안 풀리는 경우가 있다 보니 탑다운, 바텀업 차이로 인해 되고 안되고 하는 일이 없다고는 못함

[울댕별(mypuppystarpoo)]

글쿠나 바텀업 전략세우기가 넘 어려워서 고민이었는데 잘됐음 탑다운으로 정복하고 바텀업 천천히 수련해야겟음

[익명(39.113)]

메모리 제한 걸어둬서 탑다운을 강제하는 경우가 있긴 함

[익명(39.113)]

아 탑다운이래 바텀업을 강제하는 경우

[펜져(penzer27)]

나는 BFS 기반 서치면 바텀업 DFS 기반이면 탑 다운으로 접근 함.

[gglgl(222.99)]

걍 dp식이 나왔을 때, dp식의 상태간의 의존 관계를 그래프로 나타내고( dp(n-1) 값을 알아야 dp(n)을 해결 가능하면 n-1 -> n 간선이 있는걸로 생각) 이걸 위상정렬해서 순서대로 계산하는게 바텀업, 재귀적으로 짜서 메모이제이션으로 알아서 이게 돌아가게 만드는게 탑다운임. 그래서 이렇게 표현했을 때 싸이클이 발생하면 DP가 안 먹히니 이 싸이클을 해소하는 방법을 고민해보거나, 아니면 애초에 DP로 안풀리는 문제라고 생각하고 다른 알고리즘을 고민해보거나 할 필요가 있고. 어쨌든 중요한건 상태 정의고, 상태를 잘 정의하고 나면 계산해야하는 순서에 맞춰서 바텀업으로 짜든가 메모이제이션 넣어서 탑다운으로 짜든가 하는건 그냥 상황에 따른 구현 선택의 문제일 뿐임

[익명(106.242)]

그래서 탑다운<->바텀업 항상 둘 다 되는거임 안되는거임?

[익명(222.238)]

윗댓에 DAG개념으로 접근하면 상호변환 항상 가능한 거 맞음. 하지만 예외로는 한쪽방향으로 했을 때 dp표를 range update하는 경우 같은 게 있을 수 있는데 그러면 방향을 뒤집었을 때 range update 연산이 시간복잡도가 폭발할 수 있어서 안될수도 있음

[익명(211.36)]

state의 약수에서 전이되어야할땐 반대로 state의 배수로 전이해주는게 optimal하게 시간복잡도 짜기 훨씬 쉬움