[알고리즘] Dynamic Programming

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

▶️ 다음 상태를 구하기 위해 이전 상태를 저장하고 사용(Memoization)
▶️ 표를 만들어 채워가며 답을 구하는 방법
▶️ 무엇을 어떻게 저장할지 정하는 것이 중요

다이나믹 프로그래밍은 한 가지 문제에 대해서 여러번 계산하지 않고 단 한번만 풀도록 만들어주는 알고리즘이다.

🧐 접근 방식

1. 최적해의 구조적 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 상향식 방법으로 계산한다.
4. 계산된 정보로부터 최적해를 구성한다.

💡 조건

• 작은 문제에서 반복이 일어남
• 같은 문제는 항상 정답이 같음
  ➡️ 메모이제이션(memoization)으로 문제 해결
  ※ 메모이제이션(memoization) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식
  

🔢 구현 순서

1. 상태 정의

• dp 배열을 만들었을 때 index 값이 의미하는 상태
• 문제의 초기 상태를 정의 (직관적인 작은 문제의 해)

2. 점화식 구하기 : 다음 상태를 나타내기 위한 표현식
3. 시간복잡도 계산
4. 구현

🧑‍💻 구현 방법

• Bottom-up (상향식) : 작은 문제부터 차근차근 구하는 방법 (반복문 사용)
• Top-down (하향식) : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그 때 해결하는 방법 (재귀함수 사용)

⏳ 시간복잡도 : O(N)

다이나믹 프로그래밍으로 문제를 풀 때, 작은 문제부터 해결하는 것이 좋다!
문제를 풀다 보면 이전에 구했던 작은 문제들이 활용되는 것을 알 수 있다.

위 글은 아래 링크를 참고하여 작성되었습니다.
https://gyoogle.dev/blog/