Dynamic Programming(다이나믹 프로그래밍)에 대해서(Feat. 피보나치 수)

[Dynamic Programming]

 * 정의 : 특정 범위까지의 값을 구하기 위해서 그것과 다른 번위까지의 값을 이용하여 효율적으로값을 구하는
알고리즘 설계기법이다. 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 한글로 풀어 쓰면 ‘동적 계획법’이고,
약어는 DP라 한다

 

[DP의 특징]

-       Optimal~ 에 의하여 같은 문제는 구할 때마다 정답이 같아지기에 정답을 한 번 구하면 정답을 어딘가에
메모해둔다.(Memorization) 코드에선 자료구조에 저장한다.

-       각 문제는 한 번만 풀어야 한다.

 

[DP의 두 속성]

1.     Overlapping Subproblem : 겹치는 부분문제. 문제를 작은 문제로 쪼갤 수 있다.

2.     Optimal Substructure : 문제의 정답을 작은 문제의 부분에서 구할 수 있을 때 했던 계산을 계속해서 하는
방법

 

[DP의 구현 방법 두 가지]

1.     Top-Down : 큰 문제를 점점 작게 풀어나가는 방법, 재귀를 이용한다.

A.     문제를 풀어야 한다.(목표 설정)

B.      큰 문제를 작은 문제로 나눈다

C.      작은 문제를 푼다

D.     작은 문제를 풀었으니, 이제 큰 문제를 푼다.

2.     Bottom-Up : 작은 문제부터 풀어가는 방법. 보통 for문을 사용한다.

A.     문제를 크기가 작은 문제부터 차례대로 푼다

B.      문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

C.      작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다

D.     언젠간 풀어야 하는 문제를 풀 수 있게 된다.

 

[DP의 예시]

-       DP의 가장 대표적인 예시가 ‘피보나치 수’이다. 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

함수로 일반화 하면 F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n >= 2) 이다

즉, F2 = F1 + F0이고 F3 = F2 + F1 이렇게 된다.

이것을 DP알고리즘 화하면 어떻게 될까?

큰 문제는, ‘N번째 피보나치 수를 구하는 문제’가 될 것이고

이것의 작은 문제는, ‘N-1번째 피보나치 수를 구하는 문제’, ‘N-2번째 피보나치 수를 구하는 문제’가 된다.

이것을 이제 Overlapping과 Optimal 두 가지 속성으로 나누면 어떻게 될까?

1.     Overlapping Subproblem 로 피보나치 문제 알고리즘 생각해보기

A.     첫 번째 상황
* 큰 문제 : N번째 피보나치 수를 구하는 문제
* 작은 문제 : ‘N-1번째 피보나치 수를 구하는 문제’, ‘N-2번째 피보나치 수를 구하는 문제’

B.      두 번째 상황
* 큰 문제 : N-1번째 피보나치 수를 구하는 문제
* 작은 문제 : ‘N-2번째 피보나치 수를 구하는 문제’, ‘N-3번째 피보나치 수를 구하는 문제’

C.      세 번째 상황
* 큰 문제 : N-2번째 피보나치 수를 구하는 문제
* 작은 문제 : ‘N-3번째 피보나치 수를 구하는 문제’, ‘N-4번째 피보나치 수를 구하는 문제’

이런 순서로 계산하게 된다.

2.     Optimal Subproblem : 이것의 특징은 이 속성을 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다는 것이다.

예를 들어, 5번째 피보나치 수를 구한다고 할 때,

A.     10번째 피보나치 수를 구하면서 5번째 피보나치 수를 구한 값이 있다.

B.      9번째 피보나치 수를 구하면서 5번째 피보나치 수를 구한 값이 있을 떄,

C.      5번째 피보나치 수를 구하면서 얻게 된 5번째 피보나치 수는 이 세 가지 상황에서 얻은 5번째 피보나치 수는 언제나 일정하다는 특징을 갖고 있다. 그렇기 때문에 이렇게해서 얻게 된 작은 값들의 정답은 다른 곳으로 메모하게 되고, 구한 현재 값보다 작은 문제에서의 답을 구할 때 따로 계산할 필요 없이 메모한 값을 가져오면 된다.