Top-Down & Bottom-Up

다이내믹 프로그래밍을 풀면서 많이 만날 수 있는 소스 코드들이 있다.

바로 Top-Down이나 Bottom-Up이다.

 

우선 어려운말은 내가 잘못하니 쉽게 말해보겠다.

 

Top-Down = 큰 값이 들어오고 그 값을 구하기 위해 그것보다 작은 값을 가져와 조합하여 정답을 도출해 낸다.

Bottom-Up = 정답을 구하기 위해 가장 작은 값부터 차근차근 구하여 문제의 정답을 도출해 낸다.

사실 위에 글만 봐서는 잘 모른다. 왜냐하면 굉장히 비슷한 말이기 때문이다.

결과적으로 작은 값을 통해 정답을 구하는 건 공통적인 주제인 것이다.

그럼 저것의 차이가 무엇인지 알아보자.

 

◐ Top-Down 재귀함수를 이용한 방식(하향식)

재귀함수의 대표적인 예로는 피보나치의 수열이 있다. 그리고 함수호출을 줄이기 위해 메모이제이션을 사용한다.

int fibonacci(int N){
    if(N == 0) return 0;
    if(N == 1 || N == 2) return 1;
    
    if(dp[N] != -1) return dp[n];
    
    dp[N] = fibonacci(N - 1) + fibonacci(N - 2);
    return dp[N];
}

※ 재귀 함수 - 원하는 정답을 얻기 위해 직전의 자신의 함수를 활용하여 원하던 자신의 답을 찾는 것이다.

※ 메모이제이션 - 값을 빨리 불러오기 위해 값을 저장해 두는 것

메모이제이션과 DP를 혼동하는 경우가 있는데 엄연히 다르다 나중에 꼭 다루도록 하겠다.

 

◑Bottom-Up 반복문을 이용한 방식(상향식)

말 그대로 반복문이다. 당연히 피보나치를 예로 들겠지만 가장 작은 답에서 위로 천천히 올라가는 것에 포커싱을 맞춰두길 바란다.

int fibonacci(int N) {
	dp[0] = 0; dp[1] = 1;
    	for(int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
   	}
}

이리 봐도 저리 봐도 반복문을 사용한 것이 가장 눈에 띈다. 위에 것과 문제를 푸는 방식은 전혀 다르지만 같은 답을 얻어낼 것이다. 

---

위에 두 방식은 결과적으로 값만 놓고 본다면 같은 것이다. 하지만 식이 다르고 각자의 장단점이 무엇일까

 

1. Top - Down = 장점 - 이해하기 쉬운 소스코드

                          단점 - 메모리를 많이 잡아먹서 자칫 오버헤드를 발생시킬 수 있다

2. Bottom - Up = 장점 - 다이내믹 프로그래밍의 전형적인 형태, 시간과 메모리 사용을 줄일 수 있다.

                           단점 - 간단해 보이지만 복잡해질 때 읽기 어려울 수 있다.

 

처음부터 말했지만 엄청난 차이가 있는 식들이 아니다. 똑같은 피보나치로 구현을 했음에도 각자의 장단점으로 구분되었을 뿐이다. 두 개다 알아두면 좋지 않을까 싶다.