[동적계획법] 피보나치 수열

동적계획법(Dynamic Programing)이란?

 

복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법

동적계획법은 분할된 모든 경우의 수를 검토한다. 

중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 

 

 

피보나치 수열

 

F(n) = F(n-1) + F(n-2) 

 

F(n)은 F(n-1)과 F(n-2)로 나뉘어진다.

F(n-1)은 F(n-2)와 F(n-3)으로 나뉘어진다. 

.

.

.

 

이처럼 가장 큰 단위가 작은 단위로 나뉘어지는 피보나치 수열은 동적계획법으로 풀기 적합하다.

 

 

Top-Down

 

 

 

 

 

F(7)은 피보나치 수열 공식에 따라 위 그림과 같이 분할되어 간다. F(1) = 1이고 F(0) = 0이라 주어지면 다시 위로 '결합'하며 올라간다.  이때 결과를 미리 저장하여 중복계산을 방지한다. 

 

 

 

 

F(4)를 계산하려면 F(3) + F(2)를 해야한다. 그렇다고 F(2)를 다시 분할할 필요는 없다. F(3)을 계산하면서 F(2) 결과를 이미 저장했기 때문이다. 

 

결과값 저장 배열

 

 

포인터를 통해 결과가 F(3)까지 저장되었음을 알 수 있다. F(2)를 구하려면 먼저 포인터(3)와 2를 비교한다. 포인터(3)가 2보다 크므로 F(2)는 배열에 저장되어있음을 알 수 있다. 그대로 배열의 2번째 방에서 결과를 참조한다. 이런 방식을 사용하면 F(2)를 한번 더 탐색하는 비용을 줄일 수 있다.

 

 

 

 

이와같이, 분할과 결합을 반복하며 하위에서 상위로 올라가면 우리가 원하던 F(7)을 구할 수 있다. 

 

 

Bottom-Up

 

Top-Down 방식은 보통 재귀함수로 구현된다. 재귀함수는 같은 함수를 반복적으로 호출하는 방식이다. 함수는 영역(local)을 갖는다. 그래서 많이 호출되면 그만큼 스택메모리를 잡아먹는다. 엄청나게 큰 수를 구하고 싶으면 그만큼 많은 함수가 호출되므로 스택오버플로우가 발생한다. 

 

이런 Top-Down 방식의 단점을 보완한 방식이 Bottom-Up 방식이다.

 

 

 

F(0) = 0, F(1) = 1이 주어졌으므로 여기서부터 시작한다.

F(n) = F(n-1) + F(n-2), 피보나치 공식을 반복(for문) 적용하여 하나씩 구해나가는 방법이다. 

 

Bottom-Up 방식을 사용하면 함수 하나로도 원하는 값을 구할 수 있다. 

 

 

 

---

 

 

참고영상