DP(Dynamic Programming) - Top-down과 Bottom-up

Top-down / Bottom-up

DP(Dynamic Programming) 방식은 크게 두 가지로 나뉜다. Top-down 방식과 Bottom-up 방식이다.

 

두 방법 모두 큰 문제를 여러 개의 부분 문제들로 나누어 푸는 방식인데 아래의 차이가 있다.

- Top-down 방식은 가장 큰 문제를 방문한 후 작은 문제를 호출하여 답을 찾는 방식이다.

- Bottom-up 방식은 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

 

일반적으로 Top-down은 재귀 호출을 Bottom-up은 반복문을 이용하여 구현한다.

 

피보나치 문제의 구현하는 예시를 살펴보자.

Top-down

아래는 Top-down 방식의 예시이다.

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

Top-down 방식은 재귀 호출을 이용해서 구현했다. 전달해야 되는 파라미터가 많다면 Bottom-up 방식보다 많은 리소스를 사용하게 된다.

 

재귀함수가 콜스택에 점점 쌓이게 되면서 메모리도 많이 점유하게 되고, 함수를 호출하면서 이동하는 비용도 만만치 않다.

Bottom-up

아래는 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];
    }
}

반복문을 사용해서 점차 아는 범위를 늘려나간다. 재귀함수를 사용하지 않으므로 처리 시간과 리소스 사용을 줄일 수 있다.

 

---

Reference

• https://semaph.tistory.com/16