다이나믹 프로그래밍

다이나믹 프로그래밍

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 호율적으로 풀 수 있음 (시간의 효율성을 위해 공간을 사용)
• 기억하기 프로그래밍이 더 올바를 듯?
• 메모이제이션 사용: 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법
• 시간 복잡도 O(N)

DP 사용의 조건

1. 큰 문제를 작은 문제로 나눌 수 있음
2. 작은 문제에서 구한 정답은 그것을 포함한 큰 문제에서도 동일

예시

탑다운 방식

• 큰 문제를 해결 위해 작은 문제 호출
• 재귀 함수를 이용하여 DP 코드 작성

d=[0]*100 # 한 번 계산된 결과를 메모이제이션(Memoization) 하기 위한 리스트 초기화

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))

버텀업 방식

• 아래에서 위로 올라가는 방식
• 단순 반복문 이용 코드 작성

d=[0]*100

d[1]=1
d[2]=1
n=99

for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]

print(d[n])

• 다이나믹 프로그래밍의 대다수는 보텀업 방식
• 메모이제이션은 탑다운 방식에 국한되어 사용
• 웬만하면 보텀업 방식으로 푸는 것이 좋음 (시스템마다 재귀 함수의 스택의 크기가 한정되어 있을 수 있음)