다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍(Dynamic Programming)

---

• 다이나믹 프로그래밍이란?
  주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 겹치는 문제의 경우 메모이제이션 기법을 사용하여 주어진 문제를 푼다. 한마디로 분할정복 + 메모이제이션 기법이라고 할 수 있다.

다이나믹 프로그래밍의 장점과 단점

---

• 다이나믹 프로그래밍의 장점
  - 모든 가능한 경우를 확인하기 때문에 근사치가 아닌 정확한 값을 얻을 수 있다.
• 다이나믹 프로그래밍의 단점
  - 모든 가능한 경우를 확인하기 때문에 알고리즘에 비해 시간 복잡도가 크다.

다이나믹 프로그래밍의 구현

---

• 탑다운(Top-Down) 방식
  - 탑다운 방식은 재귀 호출을 사용하는 방식으로 가장 큰 문제를 먼저 호출한다. 탑다운 방식은 가독성이 좋지만, 재귀 호출의 과정에서 스택 메모리가 사용된다.
• 바텀업(Button-Up) 방식 :
  - 바텀업 방식은 반복문을 사용하는 방식으로 가장 작은 문제들부터 쌓아올린다. 바텀업 방식은 함수를 별개로 부르지 않아 시간과 메모리를 더 절약할 수 있다.

다이나믹 프로그래밍 문제

---

문제 번호	출처	난이도(5)	전체 코드	문제 풀이
1463 : 1로 만들기		1	1463.cpp	X
2193 : 이친수		1	2193.cpp	X
1904 : 01타일		1	1904.cpp	X

참고 자료

---

동적계획법(Dynamic Programming)-Ries 마법의 슈퍼마리오