Dynamic programming

Dynamic programming 이란?

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 이다 !

Dynamic(동적?) 은 아무 의미가 없다

비슷한 알고리즘으로 Divide and conquer(분할정복)가 있는데 차이점은 D.P는 중복이 있고 D&C 는 중복이 없다 라는 점이다.

📌 중복이 있다/없다는 것이 무슨 말인가?

큰 문제를 작은 문제로 나눠서 푸는 과정에서 똑같은 작은 문제가 자꾸 발생하는지,,?

핵심

• Overlapping
• Optimal Substructure
  • 큰 문제의 정답을 작은 문제의 정답에서 구하는 것이 가능하다.
    • 서울에서 부산을 가는 가장 빠른 길은 대전과 대구를 순서대로 거쳐야한다면 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야한다!
  • 한 문제의 정답은 항상 일정하다

📌  따라서 D.P 에서는 중복을 효율적으로 처리하는 것이 중요하다. 정답을 한번 구했으면 정답을 어딘가에 메모해놓자. 실제 코드에 구현할때는 배열에 저장해주면 된다. 이처럼 어딘가에 메모해놓는다고 해서 메모리제이션(memorization)이라고한다.

---

접근법

1. top-down(recursion) Or bottom- up(iteration)으로 풀면 됨
   1. 두가지 접근 방식의 시간차이? 솔직히 알 수 없다. 때에 따라 다름
2. 편한 방식으로 우선 연습 많이하자.
3. 둘 중에 한가지로만 풀리는 문제가 있으면 그건 그럼 어떡해?
   1. 그건 그때까서 공부하면 됨 지금 신경 x