[알고리즘 공부] 동적 계획법 (Dynamic Programming, DP)

동적계획법

: 어떤 문제에서 최적해를 구해야할 때, 문제를 더 이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘

 

특징

- Overlapping Subproblems

: 중복되는 하위문제가 있다.

- Optimal Subproblems

: 하위문제를 해결하면 원래문제를 해결할 수 있게 되는 구조다.

 

핵심: 초기조건 & 점화식

초기조건: 문제를 가장 작은 단위로 쪼개었을 때, 연산없이 확정되어있는 최적해

점화식: 부분 문제의 계산을 통해 전체 문제의 답을 구할 수 있도록 구성되어 있다.

 

<피보나치 수열>

#재귀 사용
def fibonacci(i):
    if i<=1:
        return i
    else:
        return fibonacci(i-1) + fibonacci(i-2)

print(fibonacci(19))

# 4181

###################################################

#DP사용
fibo=[0 for i in range(20)]
fibo[0]=0
fibo[1]=1
for i in range(2, 20):
    fibo[i]=fibo[i-1]+fibo[i-2]
print(fibo[-1])

# 4181