1. 다이나믹 프로그래밍의 개념
다이나믹 프로그래밍?
메모리 공간을 조금만 더 사용하면 연산 속도를 향상 시킬 수 있는 방법
큰 문제를 작은 문제로, 작은 문제의 정답은 큰 문제에서도 동일!
▪︎ 메모이제이션 : 한 번 구한 결과를 메모리 공간에 메모해 놓고 다시 호출되면 구해놓은 결과를 반환하는 방법(리스트, 딕셔너리 등에 저장)
- 탑다운(재귀) : 큰 문제에서 작은 문제를 호출
- 바텀업(반복문) : 작은 문제를 해결하고 큰 문제로 넘어감
2. 대표적인 예시
- 피보나치 수열
def fibo(x):
if x == 0 or x == 1:
return x
return fibo(x-2) + fibo(x-1)- 탑다운 with 메모이제이션
memo = [0] * 10 #메모할 빈 리스트를 생성
def fibo(x):
if x == 0 or x == 1:
return x
if memo[x] != 0:
return memo[x]
return fibo(x-2) + fibo(x-1)- 바텀업 with DP테이블
memo = [0] * 10 #메모할 빈 리스트를 생성
memo[1] = 1
memo[2] = 1
for i in range(3, n+1):
memo[i] = memo[i-2] + memo[i-1]3. 접근 방식
완전탐색으로 접근했을 때 시간이 너무 오래 걸리는 것 같으면, DP를 고려해보고, 부분문제들이 중복되는지를 고려해 본다.
++ 재귀는 스택오버플로우~가 발생할 수 있으므로 바텀업(반복문)을 추천
공부출처: 이것이 취업을 위한 코딩테스트다 - 동빈나
