동적 계획법 Dynamic Programming

동적 계획법 Dynamic Programming

- 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복

- 분할정복과 비슷한 느낌

 

DP 구현 2가지

● Top-down : 구현은 재귀, 저장방식은 Memoization

● Bottom-up : 구현은 반복문, 저장방식은 Tabulation

 

한 번 구한 답들은 저장해두자 Memoization

● 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록 (중복연산 방지) cache에 저장해두고 다음부턴 갖다 쓰자.

● 메모라이제이션이 아니다. 메모이제이션이다.

● 필요한 부분 문제들만 구한다 Lazy-Evaluation

● Top-down 방식에서 사용

 

쉽게 말하면, 1+1+1+1+1+1+1+1은 뭐냐고물어보고 아이는 7이라고 답한다.여기서 7을 저장해두면, 1을 더하면 8이라는것을 빠르고 쉽게 알 수 있다.

 

미리 다 구해두자 Tabulation

● 부분 문제들의 답을 미리 다 구해두면 편하다!

● 테이블을 채워나간다는 의미라서 타뷸레이션

● 필요 없는 부분 문제들까지 전부 구한다 Eager-Evaluation

● Bottom-up 방식에서 사용