동적 프로그래밍 (Dynamic Programming, DP)

동적 프로그래밍(DP)은 복잡한 문제를 작은 하위 문제로 분할하여 해결하고, 그 결과를 재사용함으로써 효율적으로 문제를 해결하는 알고리즘 기법이다. 기본적으로 동일한 문제를 여러 번 풀지 않도록 중복된 계산을 줄이는 데 중점을 둔다.

동적 프로그래밍은 최적화 문제에 많이 사용되며, 특히 최소값, 최대값 또는 경로 탐색과 같은 문제에서 자주 등장한다. DP는 하위 문제의 결과를 저장(Memoization 또는 Tabulation)해두고, 이를 기반으로 더 큰 문제를 해결하는 방식으로 진행된다.

DP 문제를 해결하는 핵심 개념

1. 중복되는 하위 문제 (Overlapping Subproblems):
   • 문제를 재귀적으로 해결할 때, 동일한 하위 문제를 여러 번 해결하는 경우가 많다. 동적 프로그래밍은 이러한 하위 문제의 결과를 저장해두어, 중복 계산을 줄이는 방식으로 최적화를 이룬다.
   • 예를 들어, 피보나치 수열은 F(n) = F(n-1) + F(n-2)이므로, 하위 문제 F(n-1)과 F(n-2)는 재귀 호출에서 여러 번 계산될 수 있다. DP를 사용하면 한 번 계산한 값을 저장하여 다시 계산하지 않도록 한다.
2. 최적 부분 구조 (Optimal Substructure):
   • 문제의 최적 해는 그 하위 문제들의 최적 해로 구성될 수 있다는 특성이다. 즉, 작은 문제들을 잘 풀면, 이 결과들을 조합하여 전체 문제의 최적 해를 구할 수 있다.
   • 예를 들어, 최단 경로 문제에서, 경로의 중간 지점까지 최단 경로를 구했다면, 이를 활용해 전체 경로의 최단 경로를 구할 수 있다.

 

DP의 두 가지 접근 방식

1. 상향식 접근 (Bottom-Up) - Tabulation:
   • 문제를 작은 문제부터 차근차근 풀어나가며, 하위 문제들의 답을 테이블에 저장하고, 이를 바탕으로 더 큰 문제를 해결하는 방식이다.
   • 이 방식은 보통 반복문을 사용하며, 계산한 값을 테이블에 저장해두고 이를 참조한다.
2. 하향식 접근 (Top-Down) - Memoization:
   • 문제를 큰 문제에서 시작하여 재귀적으로 하위 문제들을 풀어나간다. 각 하위 문제의 결과를 메모리에 저장(memoize)하여, 이미 계산된 값을 다시 계산하지 않고 바로 사용한다.
   • 이 방식은 보통 재귀 함수를 사용하여 문제를 풀며, 이미 계산된 값은 캐시에 저장하여 중복 계산을 방지한다.

 

동적 프로그래밍 예시

동적 프로그래밍의 대표적인 문제로 피보나치 수열을 들 수 있다.

1. 피보나치 수열

피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의되며, 기본적인 재귀 방식으로 풀면 중복된 계산이 많이 발생합니다. 이를 동적 프로그래밍으로 해결할 수 있다.

재귀 방식 (중복 계산 문제)

# 기본 재귀 방식 피보나치
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

print(fib_recursive(10))  # Output: 55

위 방식은 동일한 하위 문제를 여러 번 풀어야 하므로, 시간이 오래 걸린다. 중복 계산을 줄이기 위해 동적 프로그래밍을 사용할 수 있다.

상향식 (Bottom-Up) DP 방식

# 상향식 DP 피보나치 (반복문, Tabulation)
def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_bottom_up(10))  # Output: 55

하향식 (Top-Down) DP 방식 (메모이제이션)

# 하향식 DP 피보나치 (재귀, Memoization)
def fib_top_down(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_top_down(n - 1, memo) + fib_top_down(n - 2, memo)
    return memo[n]

print(fib_top_down(10))  # Output: 55

차이점:

• 기본 재귀는 동일한 하위 문제를 여러 번 계산하므로 매우 비효율적이다.
• 하향식(Top-Down)은 메모이제이션을 통해, 이미 계산된 값을 저장하여 중복 계산을 피한다.
• 상향식(Bottom-Up)은 작은 문제부터 차례대로 풀어나가며, 테이블에 값을 저장해가면서 문제를 해결한다.

 

DP 문제 해결을 위한 단계

1. 문제 정의:
   • 문제를 작은 하위 문제로 나눌 수 있는지 확인한다.
   • 하위 문제의 결과로부터 더 큰 문제를 해결할 수 있는지 확인한다.
2. 상태 정의:
   • 문제를 해결하는 데 필요한 상태(변수)를 정의한다.
   • 예를 들어, 피보나치 수열에서는 n을 상태로 두고, 각 F(n)을 구한다.
3. 상태 전이 정의:
   • 현재 상태에서 다음 상태로 넘어가는 방식(점화식)을 정의한다.
   • 예를 들어, F(n) = F(n-1) + F(n-2)와 같이 하위 문제에서 상위 문제로 전이하는 규칙을 정의한다.
4. 기저 상태 정의:
   • 가장 작은 문제(기저 사례)를 정의한다. 이는 일반적으로 재귀의 종료 조건이 된다.
   • 예를 들어, 피보나치 수열에서 F(0) = 0, F(1) = 1이 기저 상태가 된다.

 

동적 프로그래밍의 장점

• 효율성: 동적 프로그래밍은 중복된 계산을 줄여 시간 복잡도를 크게 줄인다.
• 최적화 문제 해결: DP는 최소값, 최대값, 최단 경로 등 다양한 최적화 문제를 해결하는 데 적합하다.
• 재사용 가능성: 하위 문제의 결과를 저장하여, 동일한 하위 문제가 다시 나타날 때 즉시 결과를 사용할 수 있다.

동적 프로그래밍의 단점

• 메모리 사용량: DP는 중간 결과를 저장하므로, 큰 문제일 경우 많은 메모리를 사용할 수 있다.
• 적용할 문제의 제약: 모든 문제에 동적 프로그래밍을 사용할 수 있는 것은 아닙니다. DP는 중복되는 하위 문제와 최적 부분 구조가 있을 때만 적용할 수 있다.

 

• 동적 프로그래밍(DP)은 문제를 작은 하위 문제로 나누고, 그 결과를 재사용하여 문제를 효율적으로 해결하는 알고리즘 기법이다.
• 상향식(Tabulation)과 하향식(Memoization) 두 가지 방식으로 구현할 수 있다.
• 피보나치 수열, 배낭 문제 등 다양한 최적화 문제에서 DP는 중복된 계산을 줄이고, 효율적으로 문제를 해결할 수 있다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms