Dynamic Programming : DP, 동적 계획법, 다이나믹 프로그래밍

다이나믹 프로그래밍?

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다.

 

DP와 다르게 분할 정복은 동일한 문제를 다시 푼다.

예를 들어 피보나치 수열을 분할 정복을 통해 푼다면 특정 숫자를 구하기 위해 그 n-1와 n-2 에 계속 접근한다.

즉, 반복적인 데이터 계산이 발생한다.

DP 사용할 수 있는 경우

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위의 조건을 만족할 때 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다.

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

문제를 풀 때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야한다.

완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면 DP 적용이 가능한 지, 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.

 

퀵 정렬 vs 다이나믹 프로그래밍

퀵 정렬

퀵 정렬에서도 문제를 작게 나누는 기법이 사용된다.

정렬 수행 시 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. (⇒ 분할 정복)

기준 원소(pivot)가 자리를 변경해 자리 잡으면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 원소 값을 다시 처리하는 문제는 존재하지 않는다.

다이나믹 프로그래밍

DP는 문제들이 서로 영향을 미치고 있다는 점에서 퀵 정렬과 차이가 있다.

또한 한 번 해결했던 문제를 다시금 해결한다.

그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결된 것이니 다시 해결할 필요가 없다고 반환하는 것이다. (⇒ 메모이제이션?)

 

메모이제이션(Memoization) 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류.

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.

⇒ 한 번 구한 정보를 리스트에 저장, 같은 정보가 필요할 때 이미 구한 정답을 그대로 리스트에서 가져오기 !

값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

 

보통 수열의 경우 배열이나 리스트로 표현할 수 있는데, 때에 따라 사전(dict) 등 다른 자료형을 이용할 수도 있다. an을 계산하고자 할 떄, a0~an-1 모두가 아닌 일부 작은 문제에 대한 해답만 필요하다면 사전 자료형을 사용하는게 더 효과적이다.

 

방식

탑다운(하향식) 방식과 바텀업(상향식) 방식이 있다.

 

다이나믹 프로그래밍의 전형적 형태는 Bottom-Up 방식이다!

일반적으로 반복문을 이용한 다이나믹 프로그래밍이 성능이 더 좋다. (Bottom-Up) 재귀 함수 대신에 반복문을 사용해 오버헤드를 줄일 수 있기 때문이다.

또한 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로, 가능한 Bottom-up 방식으로 구현하기를 권장한다.

recursion depth(재귀 함수 깊이)와 관련된 오류가 발생한다면 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출해 재귀 제한을 완화할 수 있다.

 

탑다운 방식(재귀)으로 비효율적 프로그램을 작성한 뒤에, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용 가능하다면 메모이제이션 기법을 적용해 코드를 개선하자.

Top-Down

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법.

큰 문제를 해결하기 위해 작은 문제를 호출한다.

메모이제이션 기법은 탑다운 방식에 국한되어 사용된다.

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

function solution(n) {  // top-down
    const dpTable = new Array(n + 1).fill(0);
    
    function fibo(x) {
        if (x < 2) return x;
        if (dpTable[x] !== 0) return dpTable[x];
        
        return dpTable[x] = (fibo(x - 1) + fibo(x - 2));
    }
    
    return fibo(n);
}

Bottom-Up

단순히 반복문을 이용하여 소스코드를 작성하는 방법.

작은 문제부터 차근차근 답을 도출한다.

‘DP 테이블’이라는 리스트에 결과를 저장한다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

function solution(n) {  // bottom-up
    const dpTable = new Array(n + 1).fill(0);
    
    dpTable[0] = 0;
    dpTable[1] = 1;
    
    // dpTable 채우기
    for (let i = 2; i <= n; i++) {
        dpTable[i] = (dpTable[i - 1] + dpTable[i - 2]);
    }
    
    return dpTable[n];
}

---

https://www.youtube.com/watch?v=5Lu34WIx2Us