DP (Dynamic Programming, 동적 프로그래밍)

DP

• Dynamic Programming, 동적 프로그래밍
• 메모이제이션을 이용하여 문제를 푼다

메모이제이션

• 다음 상태를 저장하고, 사용하기

 

 

DP..

• 난이도는 천차만별이고 처음에는 무엇을 어떻게 저장해서 써야할 지 몰라서 헤맬 수 있다 함
• 피보나치, Knapsack .....(피보나치가 두개가 아닌 세개거나, 지문이 너무 길어서 knapsack인지 모르거나..)
• 많이 풀고 생각 연습을 하는 것이 중요

 

푸는 순서

1. 상태를 정의한다.
2. 점화식을 찾는다. (구한다)
3. 시간 복잡도를 계산한다.
   • dp로 푸는 경우 시간복잡도가 다양할 수 있음
   • 1차원 배열에서 쭉 도는 O(N), 2차원 배열에서 쭉 도는 O(N^2), O(N^3)... 코테에서 삼차원 배열 이상은 잘 안나온다 함. 2차원, 3차원에서 가장 많이 나온다.
   • 반복문을 얼마나 사용했는가.. 그 과정에서 이진 탐색을 한다면 n*logn...
   • 시간 복잡도에 따라 재귀로 풀지 반복문으로 풀지 선택한다.
4. 코딩한다.

 

푸는 방법

1. Top-down (재귀)
2. Bottom-up (반복문)

• 파이썬의 경우, 재귀를 쓸 때 아슬아슬할 수 있음. 재귀로 파이썬을 푼다면 pypy나 빠른 언어를 쓰는게 좋다.
• 파이썬에서는 Bottom-up이 좀더 좋을 수 있음. 왜냐하면 점화식 그대로 반복문을 사용하면 되기 때문.