동적 프로그래밍 (Dynamic Programming)
동적 프로그래밍은
재귀적으로 구현한 알고리즘에서 중복 호출이 일어나 심각한 비효율이 발생할 때 이를 해결하는 방법이다
예를들어 피보나치 수를 아래와 같이 정의할 때
f(n) = f(n-1) + f(n-2)
f(1) = f(2) = 1
* n은 자연수
n번째 피보나치 수 f(n)(n>2)은 피보나치 수 f(n-1)와 피보나치 수 f(n-2) 를 포함한다.
이와같이 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을 때
최적 부분 구조(Optimal Substructure)를 가졌다고 하고,
아래와 같은 재귀호출로 자연스럽게 구현할 수 있다.
def fibo(n)
if n==1 or n==2:
return 1
else:
return fibo(n-1) + fibo(n-2)중복호출로 인한 비효율이 있는 함수
하지만 위 재귀함수는 매우 비효율적인데,
fibo(6)를 예로 들어보면
fibo(6) = fibo(5) + fibo(4)
fibo(6) = (fibo(4) + fibo(3)) + (fibo(3) + fibo(2))
fibo(6) = ((fibo(3) + fibo(2)) + (fibo(2) + fibo(1))) + ((fibo(2) + fibo(1)) + 1)
fibo(6) = (((fibo(2) + fibo(1)) + 1) + (1 + 1)) + (1 + 1 + 1)
fibo(6) = (((1 + 1) + 1) + (1 + 1)) + (1 + 1 + 1)
fibo(2)만 봤을 때 fibo(6)이 fibo(2)를 5번 호출한다
이러한 중복호출 횟수의 증가속도는 지수함수적이고 심각한 비효율을 초래한다.
큰 문제를 작은 문제로 쪼개서 해결할 때
작은 문제의 답을 한번이라도 구한적이 있다면
다시 계산하지 않고, 구해놓은 답을 그대로 쓰면 위와 같은 비효율이 개선될 것이다.
1. 상향식 방법
# Dp : 계산 결과들을 저장하기 위한 리스트.
# 시작 인덱스를 1로 맞추기위해서 Dp[0]에 그냥 0 넣어줌
def fibo(n)
Dp = [0, 1, 1]
for i in range(3, n + 1):
Dp.append(Dp[i-1] + Dp(i-2))
return Dp[n]위 코드는 이전의 결과를 저장해놓고 다음 연산때 이전의 결과를 사용해서
피보나치 수를 구하는 함수를 O(n)으로 개선했다
n = 1 or 2 일때 1을 반환하고
n > 2 이면 3번째 피보나치수 부터 n번째 피보나치수를 모두 구하므로.
아래부터 위로 해를 구해나가는 상향식 방법이라고 할 수 있다.
2. 하향식 방법
#전달받는 Dp는 n의 범위만큼 0으로 초기화 돼 있다고 가정
def fibo(Dp, n):
if Dp[n] != 0:
return Dp[n]
else:
if n == 1 or n == 2:
Dp[n] = 1
else:
Dp[n] = fibo(n-1) + fibo(n-2)
return Dp[n]위 코드는 그대로 재귀호출을 이용하지만, 이전의 계산결과를 이용해 중복호출 문제를 해결했다.
n부터 시작해서 답을 구해놓은적이 있으면 그대로 반환하고
그게 아니면 점점 아래로 내려가며 답을 구하므로 하향식 방법이라고 할 수 있겠다.
그렇다면 어떻게 중복호출 문제를 해결 했을까?
1) Memoization
여기서 Memoization이라는 동적프로그래밍에서 중요한 개념이 등장한다.
Dp를 초기에 모두 0으로 초기화 시키고 n에 대한 답만 Dp[n]에 저장한다면,
Dp[n] 값이
0일 때 -> 답을 구해야하고
0이 아닐때 -> 이미 답이 구해진것으로 간주 할 수 있으므로
Dp[n] 의 값에 따라 답을 구한적이 있는지 없는지 메모(Memo) 할 수 있게 되는 것이다.
2) 함수의 호출 순서
이는 함수 호출을 트리로 나타냈을때
함수의 호출 순서는 깊이 우선 탐색을 했을때의 결과와 같기 때문이다.
Dp[n] = fibo(n-1) + fibo(n-2) 에서
fibo(n-1)과 fibo(n-2)가 동시에 호출되지 않고
fibo(n-1)이 리턴된 후에 fibo(n-2)을 호출한다.
fibo(n-1) = fibo(n-2) + fibo(n-3) 이므로.
fibo(n-1)이 리턴되고 fibo(n-2)가 호출될 때 fibo(n-2)에 대한 해답이 이미 구해져 있음이 보장된다.
따라서 중복호출 횟수가 지수적으로 증가하지 않고
아래와 같이 최대 2번으로 제한된다.
1. 구해놓은 답이 없을때
2. 다른 상위 문제에서 필요로 할때 (답이 이미 구해져 있으므로 재귀호출 하지 않고 이전에 구해놓은 답을 반환 한다.)
위와 같은 하향식 방법은 프로그램 메인부에서 fibo(Dp, n)을 여러번 호출할 때
상향식 방법에 비해 성능향상이 더 있을거라고 생각한다.
상향식 방법은 한번의 호출에 대해서만 결과를 저장하지만,
하향식 방법은 메인부에서 Dp에 대한 정보를 가지고 있다면
이전에 계산해놓은 결과를 토대로 상향식 방법에 비해 적은 재귀호출을 하기 때문이다.
공부한 내용을 정리하기위해 작성한 글입니다.
지적 환영합니다!