Dynamic programming/

/*목차*/
1. 정의
2. 설명
3. Algorithm
 3.1 예제
  3.1.1 일반적인 접근
  3.1.2 Top-down
  3.1.3 Bottom-up
4. 마무리
5. 참고 자료

1. 정의

동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다.

2. 설명

하나의 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 답을 도출해내는 방법입니다. 각 하위 문제를 해결한 결과를 저장하고, 후에 같은 하위 문제가 나왔을 경우 저장했던 해를 꺼내 사용합니다. 이러한 방식으로 문제를 해결해 나가면 계산 횟수를 줄일 수 있는데, 이것이 동적 계획법의 특징 입니다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용합니다.

3. Algorithm

동적 계획법은 'Top-down'과 'Bottom-up', 크게 두 가지의 접근 방식으로 나뉩니다.

• Top-down: 하위 문제에 대한 해답을 사용하여, 어떤 문제에 대한 해답을 재귀적인 방법으로 공식화하여 해결합니다. 주로 'memoization'을 활용하여 문제를 해결하게 됩니다. 새로운 하위 문제를 풀려고 할 때마다 먼저 테이블을 확인하여 이미 해결되었는지 확인합니다. 해당 문제에 대한 해답이 기록되어 있으면 바로 사용할 수 있고, 그렇지 않으면 하위 문제에 접근하고 해결하여 해당 결과를 테이블에 추가합니다. 이것을 하향식 접근, 'Top-down'이라 부릅니다. 주로 재귀를 이용하여 문제를 해결하기 때문에 점화식을 이해하고 쉽게 적용할 수 있다는 장점이 존재하지만, 시간과 메모리를 많이 소모한다는 단점 또한 존재합니다.

• Bottom-up: 먼저 하위 문제를 해결하고 해당 결과를 사용하여 상위 문제를 해결합니다. 해당 동작을 최상위 문제를 해결할 때 까지 반복합니다. 이런 식으로 점점 더 상위의 문제에 대한 해답을 반복적으로 생성하여 전체 문제에 대한 답을 구하는 방식을 상향식 접근, 'Bottom-up'이라 부릅니다. 하향식 접근방식을 활용해 해결한 문제는 상향식 접근방식으로 문제를 재구성할 수 있습니다. 해당 방식을 이용하면 재귀를 사용하지 않음으로써 시간과 메모리를 절약할 수 있지만, 숙련되지 않았을 경우 구현에 난이도가 있습니다.

3.1 예제

밑에 나오는 예제는 Python으로 작성하였습니다.

간단한 예로는 '피보나치 수(Fibonacci number)'가 있습니다. 피보나치는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미합니다.

fibonacci_arr = [0, 1, 1, 2, 3, 5, 8 ... ...]

fibonacci_arr[2] = fibonacci_arr[1] + fibonacci_arr[0]
fibonacci_arr[3] = fibonacci_arr[2] + fibonacci_arr[1]
fibonacci_arr[4] = fibonacci_arr[3] + fibonacci_arr[2]
.
.
.
fibonacci_arr[n-1] = fibonacci_arr[n-2] + fibonacci_arr[n-3]
fibonacci_arr[n] = fibonacci_arr[n-1] + fibonacci_arr[n-2]

피보나치 수 F(n)은 결국 다음과 같은 점화식을 가집니다.

1. 1번째 항부터 시작할 경우
   F(1) = F(2) = 1
   F(n) = F(n-1) + F(n-2)
2. 0번째 항부터 시작할 경우
   F(0) = 0
   F(1) = 1
   F(n) = F(n-1) + F(n-2)

3.1.1 일반적인 접근

def fibonacci(n):
    if n == 0:
        print('call 0!')
        return 0
    elif n == 1:
        print('call 1!')
        return 1
    else:
    	print('call {}!'.format(n))
        return fibonacci(n-1) + fibonacci(n-2)

평범한 피보나치 코드입니다. 5번째 피보나치 수를 구하고자 한다면, 재귀를 통해 밑바닥까지 내려가 0을 세 번, 1을 다섯 번 호출해야 합니다. 또한 2번째와 3번째 피보나치 수를 각각 세 번, 두 번씩 계산해야 합니다. 이는 매우 비효율적입니다.

3.1.2 Top-down(하향식 접근)

def top_down_fibonacci(n):
    global dp
    
    if n == 0:
        return dp[0]
    elif n == 1:
        return dp[1]

    if dp[n] > -1:
        return dp[n]
    else:
        dp[n] = top_down_fibonacci(n-1) + top_down_fibonacci(n-2)
        return dp[n]

dp = [0, 1] + [-1 for _ in range(MAX_LIST_LENGTH)]

하향식 접근을 수행한 피보나치 코드입니다. 재귀를 통해 하위 문제로 계속 나아갑니다. 해당 하위 문제에 대한 해답이 메모이제이션을 통해 기록되어 있다면, 기록을 꺼내 사용함으로써 불필요한 중복 호출 및 계산을 줄입니다.

3.1.3 Bottom-up(상향식 접근)

def bottom_up_fibonacci(n):
    dp = [0, 1] + [0 for _ in range(n-1)]
    for i in range(2, n+1):
    	dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

상향식 접근을 수행한 피보나치 코드입니다. 하위 문제의 답을 통해 상위 문제의 답을 도출해냅니다. 도출해 낸 결과 값을 다시 저장하여 상위 문제를 해결하는 데 사용할 수 있도록 합니다. 반복문을 활용해 최상위의 답을 구할 때 까지 해당 과정을 반복하여 수행합니다. 이 방법도 또한 불필요한 계산을 하지 않습니다.

4. 마무리

정리하자면, Top-down 방식은 재귀를 통해 가장 큰 문제에서 작은 문제를 호출하여 답을 찾는 방식이고 Bottom-up 방식은 가장 작은 문제부터 답을 구해가며 전체 문제의 답을 찾는 방식입니다. 결국 DP의 핵심은 하나의 문제를 여러 개의 하위 문제로 나누어 해결하여 불필요한 연산을 줄이는 것입니다. 비유를 들자면 Top-down 방식은 '땅굴 깊숙히 들어가 안을 메우는 행위'이고, Bottom-up 방식은 '탑을 쌓아가며 올라가는 행위'라 볼 수 있습니다.

5. 참고 자료

https://en.wikipedia.org/wiki/Dynamic_programming
https://semaph.tistory.com/16

제가 찾아본 정보를 종합한 후 정리하는거라 틀린 부분이 있을 수 있습니다. 틀린 부분은 이유와 함께 지적 부탁드립니다.