Dynamic Programming

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘
  
• 시간복잡도를 계산해봤을 때 어마어마하게 많은 시간복잡도가 걸리면 대개 Dynamic Programming으로 해결하거나 다른 방법으로 풀어봐야 함

Tip

반드시 문제를 풀기 전에 완탐 시간복잡도를 계산해볼 것

• 완탐으로 접근 시 시간이 매우 오래 걸리면 다이나믹 프로그래밍 적용할 수 있는지 보아야
• 해결하고자 하는 부분 문제들의 중복 여부를 확인해 보기
• 보텀 업 방식을 권장 (재귀의 경우 recursion limit 발생 가능)

시간복잡도

시간제한에 따른 알고리즘 설계

• 시간 제한이 1초라는 가정 하의 예시

N의 max	빅오
500 (5백)	O(N³)
2,000 (2천)	O(N²)
100,000 (10만)	O(NlogN)
10,000,000 (천만)	O(N)

import time
start_time = time.time()	# 측정 시작

# 프로그램 소스코드
end_time = time.time()		# 측정 종료
print('time:', end_time - start_time)	# 수행 시간 출력

Memoization (메모이제이션)

• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
  
• 값을 저장하는 방법이므로 캐싱이라고도 함
  
• 탑다운 방식에 국한되어 사용되는 "표현"
• 보텀업 방식에서 사용되는 결과 저장용 리스트는 "DP 테이블"이라 불림
• 리스트나 Dicitionary 자료형 등을 사용 가능
• Dictionary 자료형의 경우 수열처럼 연속적이지 않은 경우 활용 가능

# 메모이제이션을 하기 위한 리스트 초기화
d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 100: 
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

fibo(99)

탑다운 방식 vs. 보텀업 방식

탑다운 방식

• 위의 피보나치 함수처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 것
• 메모이제이션 사용

보텀업 방식

• 단순히 반복문을 사용하여 소스 코드를 작성하는 경우
  
  작은 문제부터 차근차근 답을 도출해나가는 방식
  
• DP 테이블 사용

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

의문점

• 재귀함수의 시간복잡도는 어떻게 구해야 하는가?