Dynamic programming

dp와 divide and conquer

어떤 문제가 divide and conquer로 풀 수 있다고 가정해보자. 그렇다면 이 문제는 여러개의 원자적인 sub-problem들의 집합으로 볼 수 있다. 그리고 이 집합에 대해 아래의 조건이 성립한다고 가정하자.

1. atomic한 sub-problems들 중 중복(overlapping) 되는 것들이 있다.
2. 각 sub-problem들은 optimal한 substructure를 가진다. 즉, 최적해가 보장된다.

그렇다면 우리는 여기서 이렇게 생각해볼 수 있다. 중복 되는 문제들의 해를 재사용 할 수 있지 않을까? 즉, 중복 문제들의 알고리즘 인스트럭션을 처음부터 다시 전부 돌려서 값을 구하기 보다는, 이 중복을 제거 하는 방법이 있지 않을까? 그래서 연산량을 줄여볼 수 있지 않을까?

컴퓨터적으로 생각해 봤을 때 이런 중복 되는 문제들의 해를 재사용 하는 방법은 명확하다. 메모리에 저장한 후에 그걸 다시 꺼내와서 쓰면 된다. 이렇게 divide and conquer 문제에서 중복 되는 문제들의 해를 메모리에 저장 해놓고 재사용 하는 알고리즘을 dynamic programming이라고 한다.

그리고 이 dynamic programming에서 어떤 방식으로 메모리에 중복 되는 문제의 해를 저장할 것인가. 그 방법론이 두 가지가 있다.

1. memoization(top-down)
2. tabulation(bottom-up)

두 방법론에 대한 설명은 아래 reference 링크에서 잘 되어 있다.

---

REFERENCE

주니온 선생님의 유튜브 강의 : https://www.youtube.com/watch?v=yVK4PcnoMmw