다이나믹 프로그래밍(동적 프로그래밍이란?)

다이나믹프로그래밍 (동적계획법)

큰 문제를 작은 문제로 나누어 푸는 문제

• 부분문제가 중복되어 상위 문제 해결에 재활용
• Memoization 사용 o

대표적인 예시 문제로 피보나치가 있음.

분할정복과 유사하다고 느끼는 부분이 있었으나 차이점이 존재했다.

분할정복

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 푸는 알고리즘

• 부분문제가 중복되지 않는다.
• Memoization 사용 x

풀이 방법의 단계

1. DP문제인지 확인
2. 최소한의 매개변수를 활용해 상태표현식을 결정한다.
3. 점화식을 세운다.
4. 상향식(for문 을 통해) or 하향식(재귀함수를 통해)을 이용하여 문제를 해결한다.

---

2. 상태표현식 결정

상태를 나타내줄 매개변수를 최소한으로 설정하여
어떤 상태를 기준으로 문제를 풀어나갈지 결정해야 한다. << 문제를 쪼개고 점화식을 표현할 때 중요함.

다음단계와 이전관계들 사이의 관계를 찾고 점화식으로 표현할 때 중요함.