4주차에는 **다이나믹 프로그래밍(Dynamic Programming)**에 대해 공부할 예정입니다. dp는 작정하고 어렵게 출제한다면 끝도없이 어렵게 문제를 만들 수 있기 때문에 dp의 핵심개념과 원리를 이해하고 대표적인 유형들을 정복하는게 중요합니다.

4주차는 어떤 문제를 dp로 풀어야하는지, dp식 사고법은 무엇인지 감을 잡는 연습을 꾸준히 할 수 있게 문제를 구성했으니 꼭 반복적으로 풀어보시길 바랍니다.

01. 다이나믹 프로그래밍이란?

<aside> ➡️ "다이나믹 프로그래밍(Dynamic Programming)"은 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법을 의미합니다.

</aside>

[특징]

다이나믹 프로그래밍을 사용하는 알고리즘의 주요 특징은 다음과 같습니다:

1. 중복 계산 감소: 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피합니다.
2. 점화식: 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의합니다. 이를 점화식이라고 부릅니다.
3. 최적 부분 구조: 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 합니다.

[조건]

모든 해결책을 다 탐색해보는 ‘완전 탐색’은 기본적으로 높은 시간 복잡도를 가집니다. 이를 ‘체계적’이고 ‘효율적으로 탐색하기 위해서는 몇 가지 조건이 있어야 합니다.

• Overlapping Subproblems - 중복 하위 문제
  • 중복 계산해야 하는 하위 문제가 존재합니다.
• Optimal Substructure - 최적 부분 구조
  • 하위 문제에서 구한 최적의 답이 큰 문제의 최적의 답을 구할 수 있는 구조여야 합니다.

[예시1]

피보나치 수열로 예시를 들어보겠습니다.