[크래프톤 정글 ] 동적 계획법(dynamic programming)

동적 계획법(DP)는 하나의 알고리즘이라기보다는 문제를 해결하기 위한 방법론에 가깝다. 이는 문제를 작은 하위 문제들로 나누고, 그 결과를 재사용하여 최적화하는 방식이다. 동적 계획법은 문제마다 각기 다른 점화식을 세우고, 그에 맞는 알고리즘을 스스로 만들어가야 하기 때문에, 처음에는 이 방법을 쉽게 떠올리기 어려울 수 있다.

그래서, 동적 계획법의 흐름을 따라가며 개념을 이해하는 방법을 예시를 통해 정리해보고자 한다.

https://developsvai5096.tistory.com/76

위의 포스트 또한 dp를 통해 점화식을 구하는 내용이 자세히 정리 되어있다. 같이 보면 도움이 되지 싶다.

1. Reduction & Recursion (문제를 작은 문제로 나누기)

동적 계획법은 큰 문제를 작은 문제로 나누어 푸는 기법에서 시작한다. 이 단계에서는 재귀적으로 문제를 해결하는 방식이 주로 사용된다. 예를 들어, 피보나치 수열을 재귀적으로 구할 때, F(n)은 F(n-1)과 F(n-2)로 나눠진다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

이 과정에서 문제는 자연스럽게 작은 문제들로 분할되며, 이를 재귀적으로 해결한다. 그러나 이 방법은 동일한 하위 문제를 여러 번 계산하는 비효율성이 존재한다.

2. Memoization (중복 계산 방지)

재귀를 사용한 문제 해결에서 발견된 가장 큰 문제는 중복 계산이다. 같은 하위 문제들이 여러 번 호출되면서 시간 복잡도가 기하급수적으로 커지게 된다. 이를 해결하기 위해 고안된 것이 메모이제이션(Memoization)이다.

메모이제이션은 이미 계산한 값을 저장해두고, 이후에 다시 그 값이 필요할 때는 저장된 값을 재사용하는 기법이다. 이로써 중복된 계산을 방지할 수 있다.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

이 방식에서는 각 부분 문제가 한 번만 계산되므로 시간 복잡도는 O(n)으로 줄어든다. 메모이제이션은 재귀적 접근(Top-Down)과 결합되어 중복 계산을 제거하는 방식이다.

3. Iterative Approach (반복문으로 재귀 최적화)

메모이제이션을 사용해도 여전히 재귀 호출이 존재하기 때문에 스택 오버헤드가 발생한다. 이를 개선하기 위해, 재귀적 접근 대신 반복문을 사용하는 Bottom-Up 방식이 등장하게 된다.

Bottom-Up 방식은 작은 문제에서 시작해 점차 큰 문제로 확장하며 값을 계산해 나가는 방식이다. 이렇게 하면 재귀 호출에 따른 스택 사용 없이도 문제를 해결할 수 있다.

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

이 방법은 메모이제이션과 다르게, 함수 호출이 아닌 단순 반복문을 사용하므로 스택 오버헤드가 발생하지 않는다. 즉, 이 단계에서는 재귀를 제거하고 반복문만으로 문제를 해결하는 최적화가 이루어진다.

4. Further Optimization (추가 최적화)

반복문을 사용하는 Bottom-Up 방식도 다시 한 번 최적화할 수 있다. 예를 들어, 피보나치 수열의 경우, F(n)을 계산할 때 직전 두 값(F(n-1), F(n-2))만 필요하므로, 굳이 모든 중간 값을 저장할 필요가 없다. 이를 통해 공간 복잡도를 O(1)로 줄일 수 있다.

def fibonacci(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

이 방식은 필요한 메모리 공간을 최소화하면서도 여전히 O(n)의 시간 복잡도로 문제를 해결할 수 있게 한다.

복잡도와 관련된 흐름 요약

1. 순수 재귀 (Reduction & Recursion): 중복 계산으로 인해 시간 복잡도는 O(2^n)로 매우 비효율적이다.
2. 메모이제이션 (Memoization): 중복 계산을 제거하여 시간 복잡도를 O(n)으로 줄인다. 단, 공간 복잡도는 O(n)이다.
3. 반복문 (Iterative Approach, Bottom-Up): 재귀를 제거하고 반복문을 사용하여 동일한 시간 복잡도 O(n)을 유지하면서 스택 오버헤드를 제거한다. 공간 복잡도는 여전히 O(n)이다.
4. 공간 최적화 (Space Optimization): 메모리 사용을 최소화하여 공간 복잡도를 O(1)로 줄인다. 시간 복잡도는 여전히 O(n)이다.

결론

• 동적 계획법의 발전 과정은 재귀적 문제 해결 방식에서 시작하여, 중복 계산을 해결하기 위해 메모이제이션을 적용하고, 이를 더 최적화하기 위해 반복문으로 재귀를 제거하며, 마지막으로 공간 최적화까지 진행된다.
• 이러한 과정을 통해 시간 복잡도는 O(2^n)에서 O(n)으로 최적화되고, 공간 복잡도도 최적화 과정을 통해 O(n)에서 O(1)로 감소할 수 있다.