다이나믹 프로그래밍이란 한 번 계산하여 해결한 문제를 메모리에 저장하여 다음에 같은 문제를 만났을때 계산하지 않고 메모리에 저장한 값을 가져와 답을 반환하여 효율성을 높이는 방식이다.
해당 다이나믹 프로그래밍에서의 다이나믹은 다른 상황에서 쓰이는 의미가 담기진 않았다.
다이나믹 프로그래밍(DP)의 두 가지 방법
- 탑다운
하향식, 구현 과정에서 재귀함수를 사용한다. 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출
- 바텀업
상향식, 구현 과정에서 반복문를 사용한다. 아래쪽부터 작은 문제를 하나씩 해결해나가며 다음의 문제까지 차례로 해결
위 처럼 두 가지의 방법을 다이나믹 프로그래밍을 구현할 수 있다.
DP를 이용할 수 있는 조건
1. 최적 부분 조건
- 작은 문제들의 답을 모아 큰 문제를 해결할 수 있어야 한다.
2. 중복되는 부분 문제
- 동일만 문제를 반복적으로 해결하는 상황
DP로 효과적으로 계산할 수 있는 문제들
[피보나치 수열]
앞 두 수의 합으로 이루어진 수열
이러한 인접한 항들 사이의 관계식으로 표현한 것을 점화식이라고 하는데 피보나치 수열을 점화식은 다음과 같다
피보나치 수열이 계산되는 과정을 표현해보면
이렇게 표현된다.
코드로 작성해보자
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
하지만 단순 재귀함수로 피보나치 수열을 해결하면 아래 그림과 같이 되어 지수 시간 복잡도를 가지게 되기 때문에 더 효율적인 방법이 필요하다.
>> 중복되는 부분문제라고 볼 수 있다.
그리고 특정 값을 구할려고 하면 그 값이 작은 문제로 분해되는데 이는 최적 부분 구조이기 때문에
DP를 이용해 해결할 수 있다.
먼저 탑다운 방식인 메모이제이션으로 구현해보자
메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
- 같은 문제를 다시 호출할 경우 메모했던 결과를 가지고 온다.
- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
# f(99)를 구하고 싶다
dp = [0]*100
def fibo(x):
# 종료조건
if x == 1 or x == 2:
return 1
# 계산한 적이 있는 문제라면 저장한 값 반환
if dp[x] != 0:
return dp[x]
# 계산한 적이 없는 문제라면 계산하여 dp 테이블에 저장
dp[x] = fibo(x-1) + fibo(x-2)
return dp[x]
print(f(99))재귀함수를 사용하는 것을 확인할 수 있다.
바텀업 방식으로도 DP를 구현해보자
dp = [0]*100
dp[1] = 1
dp[2] = 1
n = 99
for i in rnage(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])반복문을 사용하는 것을 확인할 수 있다.
메모이제이션 동작 분석
위와 같이 계산이 되기 때문에 효율적인 것을 알 수 있다 또한 호출된 것만 남긴다면
이렇게 함수가 호출된다.
피보나치 수열로 다이나믹 프로그래밍의 기초 개념을 알아봤다. 다이나믹 프로그래밍은 거의 알려진 문제에서 나오는 경우가 많기 때문에 문제를 많이 접하고 해결하며 익숙해 지는 것이 중요한것 같다