RL : Dynamic Programming

Dynamic Programming

---

정의

시간에 따라 변하는 대상을 여러 개의 process로 나누어 계획하는 것을 말한다.

“전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식” 

1. 전체 문제를 작은 문제로 단순화한다. -> 부분 문제를 정의한다.
2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 만든다.
3. 작은 문제를 해결한 방법으로 전체 문제를 해결한다. -> 문제를 해결한다.

조건

Overlapping Subproblem란, 어떤 문제가 여러 개의 부분 문제로 나뉘는 문제를 말한다. 이는 위의 Dynamic Programming의 정의에서 이미 다룬 내용이다.

Optimal Substructure란, 어떤 문제의 최선의 해결책이 그 부분 문제의 최적의 해결책으로 부터 설계될 수 있는 경우를 말한다. 위의 예시 사진을 보면서 익히자. Start 지점에서 5,2,11의 비용을 가지는 path들이 있을 때, 5는 20, 2는 25, 11은 17 과 이어진다. 5를 지나는 path는 goal을 향해 가기 위해서는 20의 비용을 지출하는 것이 제일 최선이다.

이는 다른 path에 영향을 받지 않는다는 것이다.

Top Down  vs Bottom Up

흔히 우리가 아는 방식 중에 Top Down, Bottom Up이 존재한다.

 

Top Down 은 큰 문제를 작은 문제로 나눈다. 이는 재귀함수로 표현이 가능하다.

Botton Up 은 작은 문제를 풀고 조금 더 큰 문제를 푼다. 이는 반복문으로 구현이 가능하다.

Memoization

Dynamic Programming의 가장 큰 특징이 바로 Memoization, 메모리에 연산 값을 기억하는 것이다.

 

왼쪽 사진을 보면 피보나치 수열에 대한 Tree 구조이다. 이 때 5라는 숫자를 피보나치 함수에 넣었을 때,

1. f(5) = f(4) + f(3)
2. f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1)
3. ....

이런식으로 반복적인 연산을 해야한다.

따라서 기존에 했던 연산을 미리 메모리에 기억하고 있다면, 이러한 불필요한 반복적인 연산을 할 필요가 없다.

따라서 여러 개의 process로 나누어 작업을 빠르게 하기 위해서는 Memoization 이라는 단계가 절대적이다.

Top Down vs Bottom Up

Dynamic Programming 에서 주로 쓰는 개념 중에서 Top Down과 Bottom Up은  수학적으로는 똑같다.

하지만, 재귀는 stack을 쓰기 때문에 Top Down이 더 느리다.

왜냐하면 재귀는 함수 자신을 계속 불러오고 stack에 저장한 후, 다시 돌아가기 때문에, 재귀는 변수와 선언된 함수를 계속 부르게 된다. 따라서 Bottom Up보다 훨씬 느릴 것이다.

 

이를 메모리 구조와 엮어서 생각해보면 좋다.

 

메모리 구조

결국 Top Down은 재귀함수를 사용하기 때문에 Stack에 쌓아두는 양이 더 많기 때문에, Dynamic Programming을 진행할 때, 메모리 관점에서 봐도 속도가 느릴 수 밖에 없다.

 

Reference

출처 : 

velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm)