컴퓨터가 해결하기 어려운 문제는 시간, 메모리 공간이 매우 많이 필요한 문제들이다. 그래서 연산속도와 메모리 공간이 효율적인 알고리즘을 작성해야한다. 어떤 문제는 메모리 공간을 조금 더 사용하면 연산 속도를 엄청 증가시킬 수 있다. 이러한 케이스가 다이나믹 프로그래밍으로 해결할 수 있는 문제들이다.
다이나믹 프로그래밍의 대표적인 예시는 피보나치 수열이다. 피보나치 수열은 이전 두 항의 합이 현재항인 수열이다.
프로그래밍에서 이러한 수열을 배열이나 리스트로 표현할 수 있다. 파이썬에서는 리스트를 이용해서 처리한다.
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)이렇게 재귀함수로 피보나치 수열을 구현하면 n이 커질때 수행시간이 엄청 나게 증가한다는 문제가 발생한다. 재귀함수를 사용하면 f(3)을 매번 계산해야 된다. 굉장히 비효율적이 된다. 하지만 리스트 같은데 저장하고 불러서 사용하면 굉장히 효율적으로 사용할 수 있게 된다. 다이나믹 프로그래밍은 다음과 같은 경우에 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
메모제이션은 다이나믹 프로그래밍을 구현하는 방법중에 하나로 한 번 구현한 결과를 정장하고 다시 호출해서 사용하는 방법이다. 캐싱이라고도 부른다.
# 메모제이션을 위한 초기 리스트
d = [0] * 100
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]
print(fibo(99))메모제이션은 규칙적이지 않은 경우에는 dict형태를 활용해야 할 수 도 있다. 이전에 계산했던 일부 정보만 필요한 경우는 dict형태가 더 효율적일 것이다. 완전 탐색으로 너무 오래걸리면 다이나믹 프로그램을 활용할 수 있을지 부분 문제들에 중복이 있는지 확인해보면 좋을 것이다.
Just Do