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

이번 포스팅에서는 다이나믹 프로그래밍에 대해 다뤄보고자 한다.

 

다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀는 알고리즘 기법이다.

 

특정 조건이 만족되는 문제에서 다이나믹 프로그래밍을 사용하면, 중복되는 연산을 줄일 수 있다.

 

특정 조건은 다음과 같다.

1. 큰 문제를 작은 문제로 나눌 수 있다. (최적 부분 구조)
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (중복되는 부분 문제)

 

다이나믹 프로그래밍을 구현하는 방법은 크게 두 가지가 있다.

 

첫 번째는 Top-down 방식인 메모이제이션(Memoization) 기법이다.

메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모이제이션은 값을 저장하는 방법이기 때문에 캐싱(Cashing)이라고도 한다.

구현은 리스트를 사용한다.

 

위의 조건을 만족하는 대표적인 문제로 피보나치 수열을 예로 들 수 있다.

# 메모이제이션 하기 위한 리스트
d = [0] * 100

def fibo(x):
    # x가 1 또는 2일 경우 바로 반환하고 종료
    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))

이렇게 재귀 함수를 이용해서 구현하는 방법은, 큰 문제(fibo(99))를 해결하기 위해 작은 문제(fibo(98), fibo(92))를 호출하기 때문에 Top-down 방식이라고 한다.

 

메모이제이션은 리스트가 아닌 딕셔너리를 이용할 수도 있다.

딕셔너리는 수열처럼 연속적이지 않은 경우에 유용하다.
\(a_n\)을 계산하고자 할 때 \(a_0\) ~ \(a_{n-1}\) 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우에 사용할 수 있다.

 

 

다이나믹 프로그래밍을 구현하는 두 번째 방법은 Bottom-up 방식이다.

Bottom-up 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다.

메모이제이션은 Top-down 방식에 국한되어 사용하는 표현이다.

 

피보나치 수열 문제를 Bottom-up 방식으로 구현하면 다음과 같다.

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

# 계산을 시작하기 위한 첫 번째 수와 두 번째 수 저장
d[1] = 1
d[2] = 1

n = 99

# 반복문을 활용해 구현
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

---

문제를 작게 나누는 방법은 퀵 정렬에서도 사용한다.

그러나 차이점은, 퀵 정렬은 리스트를 분할하며 정렬이 되도록 하기 때문에 문제들이 서로 영향을 미치지 않는다.

기준 원소(pivot)가 자리를 잡으면, 다시 움직이지 않는다.

따라서 분할 정복(Divide and Conquer)알고리즘으로 분류한다.

 

다이나믹 프로그래밍의 경우, 문제들이 서로 영향을 미친다. 이미 해결된 부분 문제에 대한 답을 정해놓고, 이미 해결 됐으니, 다시 할 필요 없다며 반환하는 것이다. (메모이제이션에서는 결과를 저장해 놓고 반환한다.)

따라서 분할 정복과는 다른 것이다.

 

---

📚 참고 : 이것이 취업을 위한 코딩테스트다 with 파이썬