[DP] Top-down 과 Bottom-up 의 차이점과 장단점, 쓰는 경우

1.Top-down 과 Bottom-up

DP를 푸는 방식에는 두 가지가 있다.

Top-Down : 큰 부분부터 작은 부분으로 쪼개지며 답을 찾는다(재귀 사용)

Bottom-up : 작은 부분부터 큰 부분까지 모두 답을 찾는다. 즉  큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.

 

2. Top-down 장점

모든 부분을 다 구하지 않아도 될 때 시간복잡도 면에서 유리하다. Bottom-up 방식은 문제 해결에 필요하지 않은 부분까지 모두 구하기 때문에 메모리나 시간상 불리하다.

그 예시로 백준 무한 수열이 있다.

 

3. Bottom-up 장점

모든 부분을 다 구해야 할 때는 Bottom-up이 유리하다. Top-down은 재귀함수를 구현하기 때문에 stack이 쌓여 불필요한 메모리가 낭비될 수 있다.

그 예시로 피보나치 수 4 가 있다.

 

참고자료

https://devruby7777.tistory.com/entry/Top-down-DP%EC%99%80-Bottom-up-DP%EC%9D%98-%EC%B0%A8%EC%9D%B4%EC%A0%90%EA%B3%BC-%EC%9E%A5%EB%8B%A8%EC%A0%90-%EC%93%B0%EB%8A%94-%EA%B2%BD%EC%9A%B0