[일반] 탑다운 ㅅㅂ

[익명(223.39)]

종만북으로 입문해서 모든문제를 재귀적으로 생각하는게 익숙해졌는데

어제 C번 아무생각없이 탑다운으로 짰다가 2000*2000*2000만들어버린거 캐치못하고 냈다가 시스텟 TLE뜸

바텀업이었으면 2000*2000*2000인거 바로 눈에 보였을건데;;

오랜만에 C개쉽게 나온거 같은데 아쉽누

[시아닌(kimjg1119)]

탑다 바텀업 상관없이 2000인데 세제곱 돌린것부터 미스

[익명(223.39)]

탑다운으로 하니까 생각없이 짰을때 안보여 그게 바텀업이 이런 실수방지하기 좋은 방식인거 같음

[즈우북(175.223)]

탑다운 바텀업 문제가 아니라 그냥 시간복잡도 계산 능력이 부족한 것 같습니다..

[즈우북(175.223)]

애초에 생각없이 바로 구현에 들어가지 마시고 코드 짜기전에 시간복잡도 계산을 무조건 한 번 하고 구현하시면 뭘로 짜든 문제 없지 않을까요? 탑다운이든 바텀업이든 풀이 나온 시점에서 시간복잡도는 계산이 가능하니까여

[익명(223.39)]

그게 맞는거 같은데 탑다운 시간복잡도 계산이 좀 어려움

[익명(223.39)]

재귀함수 시간복잡도 계산이 잘안되는듯...

[즈우북(175.223)]

탑다운은 걍 (부분 문제 개수) *(부분문제 하나 계산하는데 걸리는 시간) 으로 생각하시면 편합니다 예를 들어 DP식을 세웠는데 인자가 a,b 두 개고 둘다 크기가 n이라 칩시다. 그리고 dp(a,b)를 해결하는데 반복문 한번 돌아야 돼서 O(n) 시간이 걸린다면 시간복잡도는 부분 문제 개수가 O(n^2)에 하나 푸는데 O(n)이니까 총 O(n^3)입니다

[즈우북(175.223)]

이런 식으로 추정하면 탑다운이라고 계산하기 딱히 더 어려울것도 없어요. 그리고 애초에 DP의 재귀식은 그 구현과는 무관하기 때문에 탑다운은 계산못하겠고 바텀업은 할수있는것 자체가 시간복잡도 계산 능력이 부족하다는 뜻이므로 구현 전에 재귀식만 보고 시간복잡도 계산하는 연습을 많이 하시는게 좋지 않을까 싶어요

[익명(223.39)]

점화식을 안세우고 푸는편인데 이거부터 고쳐야겠죠?

[즈우북(175.223)]

당연히.. 코딩은 점화식을 제대로 다 세워놓고 시간복잡도 공간복잡도 분석까지 끝내놓고 들어가셔야합니다