다이나믹 프로그래밍(Dynamic Programming)이란 (동적 계획법 / 동적 프로그래밍) (Top-Down, Bottom-Up)

이미지 출처 : https://s3.ap-south-1.amazonaws.com/afteracademy-server-uploads/idea-of-dynamic-programming-banner-6fd855e4c3e0896e.png

 

 

 

다이나믹 프로그래밍(동적 계획법)이란 무엇일까?

다이나믹 프로그래밍(동적 계획법)은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.

 

일반적인 분할 정복 기법(ex. 일반적 재귀로 구현한 피보나치 수열 함수)의 경우 동일한 문제를 다시 푼다는 단점을 가지고 있다.

이러한 경우에 하나의 문제를 단 한 번만 풀게해 더 효율적으로 만드는 것이 다이나믹 프로그래밍이다.

 

다이나믹 프로그래밍은 아래와 같은 가정 하에 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 가정중 두번째가 가장 핵심적인 것이다.

작은 문제에서 구한 정답이 큰 문제에서의 문제와 동일하기 때문에 작은 문제에서 구한 정답을 잠시 배열에 저장을 해놓고 나중에 큰 문제에서 그것을 요할때 단순하게 제시만 해주는 것이다.

 

그리고 실제 이미 구한 답을 잠시 기록해 두는 과정을 '메모이제이션(Memoization)'이라고 한다.

이 메모이제이션이 사용된다는 점에서 분할 정복과는 다르다.

 

즉, 간단히 얘기해서 크고 어려운 문제에 대해 그것을 잘게 나누어 각각 해결한 뒤, 이 해결한 것들을 가지고 전체의 답을 구하는 것이다. 그리고 그 과정에서 메모이제이션을 이용하는 것이다.

 

 

---

 

 

크고 어려운 문제를 잘게 나누어 해결하는 과정에서 중복된 계산을 하는 경우 컴퓨터가 연산하기에 벅찬 연산량을 줄 수 있다. 그렇기 때문에 한 번 구한 값은 배열에 저장해서 다시 그 값을 요구할 때는 이미 구한 값을 반환해주기만 하는 방식으로 컴퓨터의 중복된 연산을 줄여줘야한다.

 

 

예시를 들어 살펴보겠다.

아래는 파이썬으로 구현한 일반적인 피보나치 수열 함수이다. (숫자를 입력하면 해당 순서의 피보나치 수를 출력)

def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    return fibonacci(num-1) + fibonacci(num-2)

print(fibonacci(int(input())))

이렇게 구현하면 간단하지만 입력값이 50정도의 수만 되어도 많은 연산 시간이 필요해진다.

 

 

이 경우에 다이나믹 프로그래밍이 필요하고 아래와 같이 코딩한다.

num = int(input())

arr = [0] * (num + 1)
def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    if arr[num] != 0: return arr[num]
    arr[num] = fibonacci(num - 1) + fibonacci(num - 2)
    return arr[num]

print(fibonacci(num))

if arr[num] != 0: return arr[num]

이 코드 부분이 핵심이다. 배열에 이전의 값을 저장해두고 만약 저장해둔 값이 있다면 따로 계산하지 않고 값을 불러오는 방식의 핵심이기 때문이다.

 

 

---

 

 

동적 계획법은 구현에 있어 두 가지 방식으로 크게 나뉜다.

첫 번째 방법은 Top-Down 방식이고, 두 번째 방법은 Bottom-Up 방식이다.

 

<Top-Down>

Top-Down 방식은 위에서부터 내려오는 방식이다.

원하는 값을 먼저 부른 다음에 그 값을 이루는 작은 값들을 이용해 값들을 수집해 나가는 방식이다.

이 방식은 주로 메모이제이션(Memoization)과 재귀 함수를 써서 구현한다.

# 위의 코드와 같다.
# Top-Down 방식의 피보나치 함수 구현
num = int(input())

arr = [0] * (num + 1)
def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    if arr[num] != 0: return arr[num]
    arr[num] = fibonacci(num - 1) + fibonacci(num - 2)
    return arr[num]

print(fibonacci(num))

이 방식은 점화식을 그대로 재귀 함수로 구현하고 중간의 값들을 메모이제이션만 하면 되기 때문에 구현이 쉽다는 장점이 있다. 하지만 함수 호출 자체가 시간이 걸리기 때문에 반복문을 사용하는 Bottom-Up 방식에 비해 속도가 조금 느리다.

 

 

<Bottom-Up>

Bottom-Up 방식은 아래에서부터 올라오는 방식이다.

바닥부터 작은 값들을 차근차근 계산해 목표로 하는 전체 큰 값까지 구해내는 방식이다.

이 방식은 주로 메모이제이션(Memoization)과 반복문(for문)을 써서 구현한다.

# Bottom-Up 방식의 피보나치 수열 구현
num = int(input())

arr = [0, 1]
for i in range(2, num+1):
    arr.append(arr[i-1] + arr[i-2])
print(arr[num])

이 방식을 사용하려면 현재 위치인 인덱스 i의 값(arr[i])의 재료들(arr[i-1], arr[i-2])이 모두 구해져 있어야 한다.

이 방식은 아까 말한 것과 같이 for문을 사용하므로 함수를 호출하는 Top-Down 방식보다 조금 더 빠르다.

 

 

---

 

 

다이나믹 프로그래밍은 문제의 종류가 굉장히 많고 컴퓨터적 사고력을 요하기 때문에 코딩테스트나 코딩 대회에서 매우 자주 출제된다. 따라서 많이 연습해두는 것이 좋을 것이다.

 

 

<정리>

동적 계획법 : 큰 문제를 작은 문제로 쪼갠 다음 점화식을 구해 재귀적인 구조를 활용하여 큰 문제를 해결하는 방식

1. 큰 문제를 작은 문제로 쪼갠다.
2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 구한다.
3. 작은 문제를 해결한 방법으로 전체의 큰 문제를 해결한다.