Dynamic Programming, DP

알고리즘 기초를 풀면서 수학 문제만 풀다가 나도 남들이 말하는 dp 문제라는 걸 풀게 됐다! 뿌듯해요

 

Dynamic Programming 은 동적 프로그래밍이다. 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법 중 하나이다. 분할 정복과 유사하며 중복되는 부분 문제가 발생할 때 한 번만 계산하고 그 결과를 메모이제이션하여 다른 비슷한 부분 문제들이 다시 발생할 때 메모이제이션한 결과를 가져와 재활용한다. 

 

동적 프로그래밍을 적용하기 위해서는 두 가지 조건을 만족해야한다. 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 하는 최적 부분 구조 (Optimal Substructure) 와 부분 문제가 중복되어 여러 번 반복 계산되어야 하는 중복되는 부분 문제 (Overlapping Subproblems) 이다.

 

메모이제이션 (Memoization) 은 동적 프로그래밍 기법 중 하나로 함수의 실행 결과를 저장하여 이후 같은 입력이 들어올 때 다시 계산하지 않고 저장된 값을 불러와서 재활용하는 최적화 기법이다. 함수의 결과 값을 저장하는 캐시를 이용하여 동작한다. 함수를 호출할 때마다 입력 값에 대한 결과 값을 캐시에 저장한다. 이후 같은 입력이 들어올 때는 함수를 실행하지 않고 저장된 값을 바로 반환한다. 이렇게 하면 함수를 반복해서 호출할 때마다 계산하는 시간을 절약할 수 있으며 함수의 실행 속도를 대폭 향상시킬 수 있다.

 

메모이제이션을 사용하기 위해서는 1. 문제는 부분 문제로 나눌 수 있어야 하고 2. 부분 문제는 중복 되어야 한다. 3. 부분 문제의 해결 결과를 저장하고 재사용할 수 있어야 한다. 

 

동적 프로그래밍의 가장 큰 예시로는 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 다음 항으로 정의하는 수열이다.

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), (n >= 2)

 

동적 프로그래밍은 보통 Top-Down 과 Bottom-Up 방식으로 구현 방법이 나뉜다.

 

Top-Down 은 분할 정복과 비슷한 구조를 가지고 있다. 전체 문제를 작은 문제로 나누고 그 부분 문제들을 해결하기 위해 재귀적으로 동작한다.  이 때, 중복되는 부분 문제들을 해결하기 위해 메모이제이션을 사용한다. 이는 부분 문제의 결과를 캐시하여 재활용하는 것이다. Top-Down 방식은 일반적으로 재귀함수를 이용하여 구현하기 때문에 코드의 가독성이 높아지지만, 많은 스택 메모리를 사용할 수 있으며, 메모이제이션의 처리 오버헤드가 존재할 수 있다. 

def fib_top_down(n, memo):
    if n in memo:
        return memo[n]
    
    if n < 2:
        memo[n] = n
    else:
        memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
    
    return memo[n]

n = 10
memo = {}
result = fib_top_down(n, memo)
print(result)

 

Bottom-Up은 재귀적인 호출 없이, 작은 부분 문제들을 먼저 해결하고, 그 결과를 이용해 전체 문제의 최적해를 구하는 방식이다. 이 때, 이전에 계산한 결과를 배열 또는 리스트 등의 자료구조에 저장하고, 그 결과를 이용해 다음 계산을 수행한다. Bottom-Up 방식은 일반적으로 반복문을 이용하여 구현하기 때문에 코드의 가독성은 낮아질 수 있지만, 많은 반복문을 이용하기 때문에 스택 메모리를 사용하지 않아 메모리 절약 효과가 있으며, 메모이제이션의 처리 오버헤드가 없다.

def fib_bottom_up(n):
    if n < 2:
        return n
    
    memo = [0] * (n+1)
    memo[0] = 0
    memo[1] = 1
    
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    
    return memo[n]

n = 10
result = fib_bottom_up(n)
print(result)

 

Bottom-Up 방식은 큰 문제를 작은 문제들로 쪼개어 해결해 나가는 방식으로, 이전의 작은 문제의 결과를 재활용하여 큰 문제를 해결한다. 이 때, 작은 문제의 결과를 저장하는 배열이 필요하며, 이 배열의 크기는 입력의 크기에 비례한다. 따라서, Bottom-Up 방법은 입력 크기가 커질수록 더 많은 메모리를 필요로 하지만, 계산을 수행하는 데 있어서 효율적이며, 재귀 함수 호출을 하지 않기 때문에 함수 호출 스택의 크기를 초과하는 문제를 방지할 수 있다.

 

Top-Down 방식은 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 해결하는 방식으로, 재귀 함수 호출을 사용합니다. 이 때, 작은 문제의 결과를 저장하기 위해 배열이 필요하지 않고, 필요한 부분 문제만을 계산하기 때문에 Bottom-Up 방법보다 적은 메모리를 사용한다. 또한, 모든 부분 문제를 해결하지 않아도 되기 때문에, 필요한 부분 문제만을 빠르게 해결할 수 있다. 하지만, 재귀 함수 호출을 반복적으로 수행하면서 함수 호출 스택의 크기가 커져 스택 오버플로우가 발생할 가능성이 있다.

 

입력 값이 큰 경우 bottom-up 방식이 더 효율적이며 입력 값이 작은 경우 top-down 방식이 가독성이 높고 구현이 간단하다.