[동적 계획법] 알고리즘 - 동적 계획법 Dynamic Programming(DP)

동적 계획법(Dynamic Progamming)

하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법이다.

 

각 하위 문제를 먼저 해결하고 저장하기 때문에 같은 하위 문제가 나왔을 경우 저장한 값을 이용하여 간단하게 해결할 수 있다.

이를 통해 계산 횟수를 줄이기 때문에 하위 문제의 수가 기하 급수적으로 증가할 때 유용하다.

 

 

사용 용도

• 최단 경로 문제
• 행렬의 제곱 문제
• 최적화 문제
  ex) 문제의 숫자 범위가 크고, 경우의 수가 많은 경우 

 

 

사용 조건

- 아래 두 조건이 만족하는 경우 다이나믹 프로그래밍을 이용하여 문제를 해결하는데 유용하다.

부분 중복(반복) 문제 - 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산되는 문제

최적 부분 구조 - 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 하는 것

 

부분 중복 문제

부분 문제들이 반복되는 경향이 존재하는 구조를 말한다. 

동일한 하위문제를 반복하여 해결해야하기 때문에 메모이제이션을 활용한다.

 

최적 부분 구조

이전에 구한 연산 값을 바탕으로 다음 문제의 해를 구할 수 있는 구조여야 한다는 것이다.

ex) 어떤 경유지를 거쳐 목적지로 가는 문제. => 경유지로 가는 최단 경로(부분문제)와 도착지로 가는 최단 경로(전체 문제)로 나누어 생각해볼 수 있다. 

 

 

중복 연산과정을 줄이는 방법

중복 연산을 해결하기위해 메모이제이션(Memoization)이 도입되었다.

메모이제이션(Memoization)은 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기술이다.

 

구현 방법 

1. 재귀적 정의 찾기 : 큰 문제를 작은 하위 문제로 분할하는 방법을 찾는다. 
2. 메모이제이션(Memoization) : 하위 문제들의 해를 저장할 공간을 만든다. 일반적으로 배열을 사용하여 문제의 해를 계산하고 저장한다.
3. Bottom-up or Top-Down : 두가지 접근법 중 하나를 선택하여 해를 구해나간다.

 

 

접근법 

동적 계획법은  두 가지 방식으로 구현 가능하다.

동적 계획법을 설명할  때, 가장 기본적인 피보나치 수열의 값을 구하는 문제로 예시를 들었다.

• Bottom-Up
• Top -Down

 

Bottom-Up

아래에서 위로 문제를 접근하는 방법으로 부분 문제에서부터 문제를 해결하고 점차 큰 문제를 풀어가는 방식이다.

ex) for문

def fibo(n):
    fibo_data = [0] * (n + 1)
    fibo_data[1] = 1

    for i in range(2, n + 1):
        fibo_data[i] = fibo_data[i - 1] + fibo_data[i - 2]

    return fibo_data[n]

 

Top-Down

위에서 아래로 문제를 접근하는 방법으로 큰 문제에서 부분 문제로 쪼개가며 재귀 호출을 통해 문제를 풀어가는 방식이다.

ex) 재귀 호출

fibo_data = [0] * 100

def fibo(n):
    if n <= 2:
        return 1
    if fibo_data[n] == 0:
        fibo_data[n] = fibo(n - 1) + fibo(n - 2)
    return fibo_data[n]

 

 

장점

모든 방법을 검토해보기 때문에 가장 효율적인 값을 구할 수 있다.

 

단점

가능한 모든 방법을 고려해야한다는 단점이 있다.

 

 

TIP 최적의 해결 방법을 찾기 위해서는 문제를 잘게 쪼개고 최적 부분 구조와 중복 부분 문제를 찾는 것이 중요하다.