[Algorithm] Top-Down, Bottom-Up 이란?

들어가기 앞서,

• 일반적인 피보나치 재귀 함수 코드는 아래와 같습니다.

    def fibo(x):
        if (x == 1 or x==2):
            return x
        else:
            return fibo(x-1) + fibo(x-2)

• 만약, 위와 같은 피보나치 재귀 함수를 사용해 f(6)을 구한다면, f(3) 몇 번 호출될까요?

• f(3)은 아래와 같이, 3번 호출됩니다.

  • f(6)
    • f(5)
      • f(4)
        • f(3)
          • f(2)
          • f(1)
        • f(2)
      • f(3)
        • f(2)
        • f(1)
    • f(4)
      • f(3)
        • f(2)
        • f(1)
      • f(2)

• 따라서, 위와 같이 단순히 재귀 함수를 통해 매번 계산하는 방식은, 비효율적입니다.

  • f(n) 에서 n 이 커질수록, 반복해서 호출하는 수가 많아지기 때문입니다.
  • 피보나치 재귀 함수의 시간 복잡도는 O(2^n) 입니다.

• 따라서, 이러한 문제들을 해결하기 위해, “메모이제이션을 활용한 Top-Down 방식” 또는 “DP 테이블을 활용한 Bottom-Up 방식”이 사용됩니다.

Top-Down 방식이란?

• “재귀 함수”로 다이나믹 프로그래밍 소스코드를 작성하는 방식을 탑다운(Top-Down) 방식이라고 말합니다.

  • 큰 문제를 해결하기 위해 작은 문제를 호출한다는 의미입니다.

• Top-Down 방식에는 “메모이제이션”이 활용됩니다.

  • 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미합니다.

• 메모이제이션을 활용한 피보나치 재귀 함수 코드 (Top-Down)

    # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
    d = [0] * 100
  
    # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    def fibo(x):
        # 종료 조건(1 혹은 2일 때 1을 반환)
        if x == 1 or x == 2:
            return 1
        # 이미 계산한 적 있는 문제라면 그대로 반환
        if d[x] != 0:
            return d[x]
        # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2)
        return d[x]
  
    print(fibo(99))

• 해당 방법을 사용하면, 99번째 피보나치 수를 구했음에도 불구하고 정답을 빠르게 도출할 수 있습니다.

Bottom-Up 방식이란?

• 단순히 “반복문”으로 다이나믹 프로그래밍 소스코드를 작성하는 방식을 바텀업(Bottop-Up) 방식이라고 말합니다.

  • 작은 문제부터 차근차근 답을 도출한다는 의미입니다.
  • Top-Down 과 동일한 원리를 적용하되, 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 됩니다.

• Bottom-Up 방식에는 “DP 테이블”이 활용됩니다.

• DP 테이블을 활용한 피보나치 반복 함수 코드 (Bottom-Up)

    # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    d = [0] * 100
  
    # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
    d[1] = 1
    d[2] = 1
    n = 99
  
    # 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
    for i in range(3, n + 1):
        d[i] = d[i - 1] + d[i - 2]
  
    print(d[n])

추가

• 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데,
• 엄밀히 말하면 메모이제이션은, 이전에 계산된 결과를 일시적으로 기록해 놓는, “넓은 개념”을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념입니다.
• 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있습니다.

결론

• 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식입니다.
• 탑다운 방식은, 재귀 함수를 호출하며 메모리에 적재되는 일련의 과정으로 인해 오버헤드가 발생할 수 있습니다.
• 따라서, 가능하다면 재귀 함수를 사용하는 것 보단, 반복문을 사용하는게 오버헤드를 줄일 수 있는 방법입니다.

참고

• 이것이 취업을 위한 코딩 테스트다. with Python