정의?
동적 프로그래밍이란 무엇일까...
쉽게 설명한 정의를 보면 큰 문제를 작은 문제로 나누어 해결할 때 메모리의 낭비없이 효율적으로 해결하는 방식이라고 한다.
이를 위한 사용조건으로는 2가지가 있는데,
첫 번째는 최적부분구조이다. 이는 큰 문제를 작은 문제로 나누어 해결이 가능하다는 조건이다.
두 번째는 중복부분문제이다. 이렇게 나누어진 문제를 반복적으로 해결할 수 있는 중복된 부분이 있다는 조건이다.
분할 정복과는 다른데, 여러 차이점이 있으나, 우선 분할 정복은 동일 문제가 반복적으로 발생하지 않는다는 점에서 차이점이 있다.
결국 동적프로그래밍은 문제에 대한 귀납적인 추론을 통해 문제를 해결하는 과정이라고 볼 수있다.
귀납적 사고
귀납적 사고란. 개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어거나 혹은 역으로 보편적인 상황에서 구체적인 상황으로 유도하는 추론 형식 · 추리 방법이다.
쉽게 말하면 개별적으로 작은 여러 문제들이 가진 반복성, 규칙성을 발견하여 일반적인 사실이나 원리로서의 결론을 도출해내는 것이라고 할 수 있다.
메모제이션을 활용한다. DP에 국한되는 개념은 아닌데, 한 번 계산한 결과를 메모리 공간에 기록하는 것이다.
기록된 결과는 호출하면 그대로 가져와진다.
기록한다는 점에서 캐싱(Caching)이라고 한다.
활용 방법
동적 프로그래밍의 활용 방법으로 크게 2가지가 있다. 탑다운(상향식) 과 바텀업(하향식)이 있다.
상향식 관점에서 문제를 해결하기 위한 방법은 먼저 점화식을 통해 작은 문제를 해결하여 저장하고 작은 값부터 계산하여 해결하는 방식이다. 즉 작은 문제의 답을 모아 큰 문제를 해결하는 것이다.
하향식 관점에서 문제를 해결하는 방식은 메모이제이션을 통해 저장된 연산결과를 호출하는 방식이다. 이미 연산이 완료된 값이면 해당 값을 호출하고, 연산되지 않은 값이면 점화식에 따라 새로운 값을 저장한다. 즉 큰 문제를 작은 문제로 나누어 해결하는 방식이다.
동적 프로그래밍을 통해 이미 계산된 결과를 메모리에 기록하면 필요한 연산만 진행할 것을 기대할 수 있다.
메모이제이션을 사용하게 될 경우 시간복잡도는 이다.
피보나치 수열 (예시)
대표적인 동적프로그램의 활용 예로는 피보나치 수열이 존재한다.
피보나치 수열이란 0과 1로 시작하는 수열로. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
문제에 답이 있긴 하다. 피보나치의 수열의 특징은 2번째부터 바로 앞의 두 피보나치 수의 합이라는 것이다.
동적 프로그래밍은 이러한 반복적인 부분을 찾고 문제를 해결하는 관점을 가져야한다.
이는 곧 문제에 대한 귀납적인 정의를 내려야 한다는 것이다.
수학적 문제를 해결하기 위한 귀납적 방식은
- 초기 조건을 먼저 제시하고
- 점화식을 제시하는 것이다.
해당 문제는 초기 조건이 제시 되어 있다.
0번째의 수는 0이고, 1번째의 수는 0이며 2번째부터 바로 앞 두 수의 합이다.
이를 점화식으로 나타내면 다음과 같다.
이러한 점화식을 바탕으로 다음과 같이 구현하였다.
### top-down
import sys
sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline
n = int(input())
d = [0] * (n+1)
def fibo(x):
if x == 0:
return 0
elif x == 1 or x == 2:
# i가 1이나 2면 바로 return
d[x] = 1
return d[x]
elif d[x] != 0:
return d[x]
# 값이 저장되어 있는 경우 값을 출력함.
else:
d[x] = fibo(x-2) + fibo(x-1)
return d[x]
# 값이 저장되어 있지 않은 경우 값을 저장함. (메모이제이션)
print(fibo(n))
### bottom up
import sys
sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline
n = int(input())
dp = [0] * (n+1)
# dp테이블 초기화
if n == 1:
dp[1] = 1
if n == 2:
dp[1] = dp[2] = 1
if n > 2:
dp[1] = dp[2] = 1
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
# 밑에서부터 n까지 반복해서 올라감
print(dp[n])
