04 다이나믹프로그래밍 (DP)

* 다이나믹 프로그래밍이란?

#4 다이나믹 프로그래밍 ( Dynamic Programming )이란, 큰 하나의 문제를 작은문제 여러개로 나누어 푸는 문제이다. 이름에 들어가는 Dynamic은 문제 방식과 아무 관련이 없다.

큰 하나의 문제를 작은 문제로 나누어 푸는것에는 두가지 문제 풀이가 존재하는데, 첫 째는 앞서말한 다이나믹 프로그래밍으로 푸는방법과 두번째로는 분할정복 풀이법이다. 이 두 문제풀이법의 차이는 DP는 문제를 풀때, 중복이 발생하고 분할정복은 중복이 발생하지 않는다는 것이다.

예를 들면, 40명의 학생이 존재할때, 40명을 10명 30명으로 나누고 또 그 30명을 10명 20명 20명을 10명 10명으로 나눈다면, 총 10명의 집단이 4개가 존재한다. 이렇게 10명의 집단이라는것이 4번 중복될수 있음을 뜻한다.

반면에 분할정복은 40명의 학생을 왼편 오른편으로 나누는 방식등 중복을 허용하지 않는다.

* 어떤문제를 다이나믹프로그래밍으로 풀수있나?

1. Overlapping Subproblem : 겹치는 문제 (=중복이 발생하는문제)

2. Optimal Substructure : 최적부분구조 문제 (= 문제가 작은문제의 답으로 인해 풀리는문제)

1과 2의 예시를 피보나치 수열을 이용하여 들어보겠다. (피보나치 수열이란 N 번째의 수가 N-1 번째와 N-2번째 수의 합으로 만들어지는 수열을 의미한다. ) 

1. F0 =0, F1=1 , Fn = Fn-1 + Fn-2 (n >=2) 은 피보나치의 점화식이다. 이때 상대적으로 Fn은 Fn-1, Fn-2보다 큰 문제다.

이렇게 큰문제를 작은문제로 풀수있으며, Fn-1을 구하기위해선 Fn-2와 Fn-3의 합이 필요하다. 그런데 Fn-2는 또 Fn을 구하기위해 사용된다. 이렇게 구해야하는 수가 계속 중복된다.

2. 문제의 정답은 항상 같아야한다. 10번째의 피보나치 수를 구할때, F4의 값이 필요하다. 또 9번째의 피보나치 수를 구할때도 F4의 값이 필요하다 (...중략) 이때 10번째 피보나치값의 F4와 9번째 피보나치값의 F4의 값은 일치한다. 정답은 바뀌지 않는다. 

이렇게 Overlapping Subproblem과 Optimal Substructure를 이용하여 문제를 풀어야한다. 문제의 정답이 변하지않는데, 계속 이 작은문제를 구해야한다면, 한번 구한후에 메모를 해놓는다. 그렇게한다면 문제를 푸는 시간을 단축시킬 수 있다.

* 구현방법에는 어떤게 있을까?

1. Top Down 2. Bottom-up 방식이 있다.

Top Down 방식은 주로 재귀를 사용하고, Bottom-up은 반복문을 사용한다. Bottom-up방식은 말그대로 밑에서부터, 작은 풀이부터 해나가서 큰 문제를 해결하는 방법이고, Top Down은 큰문제에 먼저 접근하여 작은문제를 푸는 방법이다.

나에게는 Bottom-up방식이 편한것같다.