Dynamic Programming

개요

 

아래 링크를 참고하여 Dynamic Programming 이 뭔지 알아보자.

유튜브 링크: https://youtu.be/vYquumk4nWw

 

 

유튜브 내용

 

피보나치 수열은 재귀 함수를 이용하여 값을 구할 수 있는 대표적인 경우이다.

이때 문제는 Recursion 을 사용하면 중복된 연산이 반복된다는 것이다.

불필요한 반복, 중복을 짱 싫어하는게 개발자이다.

 

일단은 Recursion 으로 피보나치 수열의 답을 알아보고,

Memoize 와 Bottom-up 방식으로 문제를 풀어가보자.

 

1. Recursion: 재귀적으로 문제를 해결 2. Memoize: Top-down 방식으로 볼 수 있다. Memorize 가 아님에 주의 3. Bottom-up: 아래에서 부터 차근차근 올라감. 재귀적 호출을 사용하지 않는다.

 

* 아래 이미지들은 유튜브 링크( https://youtu.be/vYquumk4nWw )를 캡처한 것이다.

 

	재귀 함수를 이용해보자.   1) 가장 기본이 되는 n == 1, n == 2 일때의 값을 정해주고, 2) 피보나치 수열의 정의대로 n 일때의 피보나치 수열의 값을 재귀적으로 계산해낸다.   문제는 그림의 오른쪽과 같이 fib(2) 는 3번, fib(3)은 2번, 이런식으로  연산이 중복해서 발생한다는 것이다.   이때의 시간복잡도는 O(2n) 이나 된다.
	Memoize 를 사용해보자.   1) memo[n]  이라는 저장공간을 하나 만들어두고 2) 한번 연산한 피보나치 수열의 값을 저장해두는 것이다.
	Memoize 의 시간복잡도를 계산해보자.   쉽게 이야기하자면 def fib() 함수를 몇 번이나 호출할 것인가 하는 거다.   1) memo[n] 에 값이 있다면 O(1) 번 불릴 것이고 2) n == 1, n == 2 라면 O(1) 번 불릴 것이다. 3) 그렇지 않은 경우에는 특정 값 n 에 대하여 fib(n-1), fib(n-2) 가 불릴테니 2n 번 불린다.   결국 O(2n+1)* O(1) = O(2n+1) = O(n) 이 된다. → 사실 시간 복잡도는 봐도봐도 소화가 안된다. ㅠ,.ㅜ)
	Bottom-Up 을 보자   Memoize 와 차이가 없어보지만, 재귀적인 부분이 없다는 것이 장점이다. 이게 왜 장점인가? 재귀적 함수란 함수가 함수를 Call 하는게 이어지는거다. 파이썬은 재귀의 한도를 정해주는데 그것이 넘어버릴 수 있는 것이다.   * 에러 메시지 참고: "maximum recursion depth exceeded"
	왼쪽은 유튜브에서 제공하는 구현 코드이다. 참고

 

Implement in Golang

 

연습의 차원에서 Golang 으로 짜봄

- https://github.com/nicewook/dynamic_programming

 

소스코드	테스트 / 벤치마크 코드

 

테스트   1) 기본 testing 패키지에 2) "github.com/stretchr/testify/assert" 를 사용하였음	벤치마크   각각의 벤치마크를 돌렸는데 fib 는 1번만 돌려보고, 피보나치 50 까지만  계산했는데도 38,369,089,000  ns 소요. = 약 38초 fibMemoize 는 피보나치 1500 까지 계산을 무려 200,000 번 해봤는데 평균 7777 ns 소요 fibBottomUp 은 피보나치 1500 까지 계산을 무려 500,000 번 해봤는데 평균 2857 ns 소요됨