Dynamic Programming

너무 어려워요

동적 계획법 (DP)

• 하나도 다이나믹 하지않다고 한다. 그냥 멋있어 보이려고 붙인 이름..?

  • 런타임 중 발생하는 것을 다이나믹이라고 하면 이것과 관련은 없다고 한다..

• 문제를 쪼개서 작은 문제의 답을 구한다음, 그걸 가지고 더 큰 문제의 답을 구하는 것을 반복

• 분할정복과 비슷한 느낌인가?

DP 구현 2가지 방법

	Top-down	Bottom-up
구현	재귀	반복문
저장 방식	Memoization(메모이제이션)	Tabulation(타뷸레이션)
장점	직관적이라 가독성이 좋음	재귀보다 (많이) 빠르다
단점	depth가 깊어질수록 성능 저하	점화식을 도출 해야한다.

• 두 방식다 공통적으로 테이블(dp)이라고 부르는, 배열 같은 것을 생성한다.

메모이제이션 Memoization

• 한 번 구한 답을 또 구하지 않도록 캐싱(dp 테이블)에 저장해두고 가져다가 사용한다 -> 중복 연산을 방지

• 필요한 부분 문제들만 구한다.

타뷸레이션 Tabulation

• 부분 문제들의 답을 미리 다 구한다. -> 필요하지 않은 답들까지 모두 구한다.

• 테이블을 채워간다는 의미에서 타뷸레이션이다.

• 사용하지 않을 답까지 전부 구한다.