[알고리즘] 동적 계획법

동적 계획법(Dynamic Programming; DP)

💡 언제 쓸까?

어떤 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있다면 이를 최적 부분 구조를 가졌다고 하는데, 이러한 성질을 가지는 문제들을 dp로 풀 수 있다.

🤷 정자역에서 서울시립대까지 가는 법?
👦 정자역에서 회기역까지 가서, 10분 걸으면 돼!
🤷 그럼 회기역까지 가는 법을 알면 되겠네. 회기역까지 어떻게 가는데?
👦 정자역에서 왕십리역까지 가서, 경의중앙선 타면 돼!
🤷 그럼 왕십리역까지 가는 법을 알면 되겠네. 왕십리역까지 어떻게 가는데? ...

💡 포인트

• 최대한 중복되는 부분을 구해서 이전에 계산한 값(벡터나 배열에 저장해둠)을 사용한다는것!
• 매번 값을 계산하는게 아니라 이전에 계산한 값을 사용해서 계산을 최소화함
  • 메모이제이션
• 관계식 구하는거 모르겠으면, 메모이제이션 배열에 어떤게 들어가면 좋을지 생각해본다!
  • 배열의 값 = 문제에서 구하고자 하는 값(혹은 그와 관련된 핵심값)
  • 최종적으로 k일때(특정 상황)의 값을 구하고자 한다면, 1부터 k까지 차곡차곡 DP배열 값(DP[1], DP[2], ..., DP[k] 순서대로 이전 인덱스의 DP값을 이용해 다음 인덱스의 DP값을 채움)을 쌓아가서 최종적으로 DP[k]를 구하면 된다

1. 예시를 직접 손으로 시행해본다
2. 중복되는 부분을 찾는다
3. 관계식을 세운다
   • ex. dp[n][p] = dp[n][p+1] + dp[n-1][p]
   • 맨 처음 값을 알아야 관계식을 통해 다음 값을 구할 수 있다
4. 이전에 계산한 값(중복되는 값)을 사용해 최종값을 구한다

💡 참고문제

• 12865 평범한 배낭

  • 참고블로그
  • 풀이

• 2293 동전1

  • 풀이

• 1149 RGB 거리

  • 풀이