[FE - ConnecTo] DAY49 TIL👩🏻‍💻

22.09.20 수업 시간 중 스스로 공부한 내용들을 정리하였습니다 😊
피드백은 언제나 환영입니다! 🍊

DP란?

DP는 다이나믹 프로그래밍(동적 계획법)이라고도 하며, 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있습니다.

---

DP를 왜 쓰는 것인가?

일반적인 재귀방식과 매우 유사하지만, 일반적인 재귀를 단순히 사용시, 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 차이점이 있습니다.

DP를 이용하면, 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용이 가능한데, 이렇게 되었을 때, 반복할 필요없이 효율적으로 문제를 해결할 수 있게 됩니다.

시간 복잡도를 기준으로는 O($n^2$) → O($f(n)$)으로 개선이 가능합니다.

---

DP는 언제 사용이 가능한가?

1. 겹치는 부분 문제(Overlapping Subproblems)

   DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구합니다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능합니다.

   DP는 부분 문제의 결과를 저장하여 재계산 할 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면, 재사용이 불가능하므로 부분 문제가 중복되지 않는 경우에는 사용할 수 없습니다.

2. 최적 부분 구조(Optimal Substructure)

   부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미합니다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일합니다.

---

DP 사용하기

DP는 특정한 경우에 사용하는 알고리즘이 아니라, 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있습니다.

보통은 DP를 사용하기 전에는 아래의 과정을 거쳐서 진행할 수 있습니다.

1. DP로 풀 수 있는 문제인지 확인하기
2. 문제의 변수 파악
3. 변수 간 관계식 만들기(점화식)
4. 메모하기
5. 기저 상태 파악하기
6. 구현하기

---

📚 출처

• https://hongjw1938.tistory.com/47