Dynamic Programming - 동적계획법 알고리즘
= "한번 계산한 문제는 다시 계산하지 않도록 한다!" 라는 목적으로 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법, divide and conquer를 이용하는 것이 특징이다.
아래 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다.
큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
대표적인 문제로 피보나치 수열을 보자.
파이썬의 재귀함수로 단순 구현한다면 다음과 같다.
import time
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
for num in range(5, 40, 10):
start = time.time()
res = fibo(num)
print(res, '-> 러닝타임:', round(time.time() - start, 2), '초')5 --> 러닝타임: 0.0 초
610 --> 러닝타임: 0.0 초
75025 --> 러닝타임: 0.04 초
9227465 --> 러닝타임: 3.36 초
위와 같이 재귀함수로 구현하면 x값이 커질수록 연산 수행시간이 기하급수적으로 늘어난다.
그렇기 때문에 다이나믹 프로그래밍을 사용하여 한번 결과를 계산한 것은 메모리에 저장해놓고 다음에 똑같은 결과가 필요하면 다시 연산하지 않고 바로 가져다 쓰는 것이다.
import time
d = [0] * 50
def fibo(x):
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]
for num in range(5, 40, 10):
start = time.time()
res = fibo(num)
print(res, '-> 러닝타임:', round(time.time() - start, 2), '초')5 --> 러닝타임: 0.0 초
610 --> 러닝타임: 0.0 초
75025 --> 러닝타임: 0.0 초
9227465 --> 러닝타임: 0.0 초
단순 재귀함수로 구현한 것과는 다르게 x가 증가해도 러닝타임은 크게 증가하지 않는 것으로 확인할 수 있다. 이것이 메모제이션 기법을 활용한 Top-Down 방식으로 큰 문제를 해결하기 위해 작은 문제를 호출하는 것이다.
반면 재귀함수를 아예 사용하지 않고 단순 반복문을 사용해서도 다이나믹 프로그래밍을 구현할 수 있다.
d = [0] * 100
d[1] = 1 # 첫 번째 항
d[2] = 1 # 두 번째 항
N = 99 # 피보나치 수열의 99번째 숫자는?
for i in range(3, N+1):
d[i] = d[i-1] + d[i-2]
print(d[N])위와 같은 방식은 작은 것부터 차근차근 답을 도출하여 큰 문제를 해결하는 bottom-up 방식이다.
top-down 방식에서 이미 수행한 결과를 저장하는 것을 메모제이션이라고 하고 사전 자료형을 이용하면 연속적이지 않은 자료의 일부를 구하기 위해 유용하다.
bottom-up 방식에서 작은 것부터 수행한 결과를 저장하는 것은 DP 테이블이라고 한다.
여기까지 동적프로그래밍에 대해 기초를 알아보았고, 백준 1003번 문제를 풀어보겠다.
1003번: 피보나치 수열
N이 주어지고 n이 N개 주어진다.
피보나치수열 0번째 항이 0, 1번째 항이 1이라고 가정하고, n번째 수를 구하기까지 0번째 항과 1번째 항이 몇번 호출되는지 구하는 문제이다. 먼저 재귀함수를 이용해서 0과 1이 호출될 때마다 count_0과 count_1을 증가시켜가는 방법으로 코드를 작성해보았다.
import sys
T = int(sys.stdin.readline())
global count_0, count_1
def fibo(x):
global count_0, count_1
if x == 0:
count_0 += 1
return 0
if x == 1:
count_1 += 1
return 1
return fibo(x-1) + fibo(x-2)
for t in range(T):
count_0 = 0
count_1 = 0
a = int(sys.stdin.readline())
fibo(a)
print(count_0, count_1)그러자 돌아가기는 하지만 시간초과가 뜨는 것을 확인했다. 그래서 배열을 이용해 패턴을 찾아 구해보기로 했다.
n = 0 일 때 (1,0)
n = 1 일 때 (0,1)
n = 2 일 때 (1,1)
n = 3 일 때 (1,2)
n = 4 일 때 (2,3)
n = 5 일 때 (3,5)
n = 6 일 때 (5,8)
'''''
여기서 각 항은 앞의 두 항을 더한 값이라는 걸 확인할 수 있고,
각각의 항을 배열로 나타내면,
count_0 = [1, 0, 1, 1, 2, 3, 5, 8, ''']
count_1 = [0, 1, 1, 2, 3, 5, 8, 13, ''']
이렇게 나타난다. 이 패턴을 통해 배열을 구하는 코드를 작성하였다.
N = int(input())
for n in range(N):
a = int(input())
'''
if a == 0:
print(1,0)
continue
'''
count_0 = []
count_1 = []
for i in range(a+1):
if i == 0:
count_0.append(1)
count_1.append(0)
elif i == 1:
count_0.append(0)
count_1.append(1)
else:
count_0.append(count_0[i-1]+ count_0[i-2])
count_1.append(count_1[i-1]+ count_1[i-2])
print(count_0[a], count_1[a])
시간 초과가 뜨지 않고 돌아가는 것을 확인할 수 있다.
