동적 계획법(다이나믹 프로그래밍)

피보나치에 대한 동적 계획법 예제 코드이다.

global list1
list1 = [0] * 41

def fibo(a):
    if list1[a] != 0:
        return list1[a]
    if a == 1 or a == 2: list1[a] = 1
    else:
        list1[a] = fibo(a-1) + fibo(a-2)
    print("list1[%d]= %d "%(a,list1[a]))
    return list1[a]

print(fibo(20))
# 0번째부터 n번째까지 1,2번 인덱스가 1이라는 것을 알기 때문에
# 이 값들로 3, 4, 5번째값을 차례로 더해가면서 값을 넣음.
# 상향식 접근

재귀 함수는 중복 호출이 많이 일어나기 때문에 메모리를 많이 차지하고 반복문을 돌렸을 때보다 속도가 느려진다. 이러한 문제점을 보안하기 위해 동적 계획법(다이나믹 프로그래밍)을 사용한다.

동적 계획법

• 메모리제이션 기법을 사용한다. 메모리제이션 기법은 리스트를 전역 변수로 생성하고 호출된 값을 저장하고 중복 호출이 발생하면 해당 값을 가져와 사용한다.