Top-down 방식과 Bottom-up 방식

허찬·2022년 3월 3일
3

Algorithm Study

목록 보기
2/4
post-thumbnail

다이나믹 프로그래밍 문제를 푸는 방법으로는 크게 두 가지, 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];
     }

    여기서 dp[n]에 피보나치 수열의 값을 저장함으로써 메모이제이션 기법을 사용하였다.


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];
    }

    보다시피 반복문을 사용해 구현하였다.

다이나믹 프로그래밍 문제를 풀 때는 이 두 방식 중 '어느 것이 더 낫다'고 콕 집어서 말하기가 힘든 것 같다. 문제들 중에는 두 방식의 구현 난이도가 굉장히 다른 경우가 존재하기도 한다. 따라서 두 방식 모두를 잘 숙지하고 있어야 하겠다.

profile
나 허찬

0개의 댓글