[TDD] 피보나치수열

안녕하세요.

초급 개발자의 TDD 공부기입니다.

TDD 공부 할 겸? 알고리즘 공부를 해보기 위해
TDD를 이용한 알고리즘 학습을 주제로 포스팅을 시작해보려합니다.

테스트 주도 개발^[각주:1] 보면서 TDD를 맛보고

일단 키보드로 두들기면 익혀보기로 했습니다.

환경: java8, junit4

github 주소 : https://github.com/gintire/algorithm/tree/master/algorithm

 먼저 다음과 같이 Fibonacci 클래스와 FibonacciTest 클래스를 만들어줍니다.

Step	/src/main/java/Fibonacci.java	/src/test/java/FibonacciTest.java	결과
Step1	2. fib함수가 0을 대입했을 경우 0을 반환하는건 확실하므로 먼저 상수 0을 반환합니다.	1. 먼저, 다음과 같이 테스트 케이스를 작성합니다. - TC > Fibonacci 클래스의 fib함수에서 (0)을 삽입하였을 경우 0이 나온다. - 현재 fib 함수를 만들지 않았다면, 빨간줄이 그어질 것입니다.  (네. 저는 미리 만들어놔서 빨간줄이 없네요...)	3. Alt + shift + x -> t를 누르면 테스트 케이스가 돌아갑니다.  - 네!!! 성공적으로 첫번째 테스트를 통과하였습니다.
Step2	2. 0을 특별한 경우로 다루는 방법을 씁니다.	1. 두번째, 피보나치의 두번째 수 1을 넣으면 1이 반환 되는 TC를 추가합니다. - 0을 넣든 1을 넣든 Step1의 Fibonacci.fib(n)은 상수 0을 반환하므로 새로 생성한 TC를 돌리면 아마 틀렸다고 나올것입니다. - 네... 하나하나 캡쳐하긴 너무 많아서 fib(n)을 수정후 TC를 돌렸습니다.	3. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. - 성공적으로 두번째 테스트도 통과하였습니다.
Step3		1. 테스트 케이스를 아래로 중복으로 생성시켜주는게 성가시게 느껴집니다. - 입력과 예상값으로 구성된 테이블을 통해 테스트가 돌아가게 하면 단언의 공통 구조를 추출할 수 있습니다.	2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. - 정상적으로 동작합니다.
Step4		1. 테스트 케이스를 하나 더 추가해봅니다. - 운이 좋게 피보나치 수열은 0,1,1,2,3.... 이렇게 늘어나기 때문에 다음 TC 도 정상적으로 돌아 갈것 같습니다.	2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. - 잘 동작합니다.
Step5		1. 4번째 테스트 케이스를 추가해본니다. - 역시 이제는 실패할것 같은 기분이듭니다.	2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. - 실패 !!  이유를 보면 결과는 2를 예상했지만 1을 반환했다고 합니다. 당연, fib(n)은 0이 아니면 1을 반환하게 되있습니다.
Step6	1. 두번째 예외사항을 줍니다.  - 이전의 전략 ( 더 작은 입력값을 특별한 경우로 다루는 것)을 똑같이 적용하여 다음과 같이 작성합니다.  - 일반화를 하면 2는 실제로 1+1을 의미합니다.		2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다.  성공적으로 돌아갑니다!!
Step7	1. 첫번째 1은 fib(n-1)로 볼 수 있습니다.		2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. 성공적으로 돌아갑니다.
Step8	1. 두번째 1은 fib(n-2)로 볼 수 있습니다.		2. Alt + shift +x -> t를 누르면 테스트 케이스가 돌아갑니다. 성공적으로 돌아갑니다!!!!!!

흠 ... 켄트 백님의 TDD를 사용해서 알고리즘을 푸는 것을 따라 해보았습니다.

느낀점은 구현을 할 때 TDD를 사용하면,

시간복잡도를 감안하여 코딩하기엔 부적절하지 않나 생각됩니다.

현재 풀이법으로 구현은 가능하지만 시간복잡도가 O(n^2)입니다.

순환적인 피보나치 수열을 하나의 함수 호출이 두개의 함수호출로 나뉘어지는 바이너리 트리 형태입니다.

즉, fib(n)

/            |

fib(n-1)         fib(n-2)

/         |                /   |

fib(n-2)  fib(n-3)    fib(n-3)   fib(n-4)

위와 같이 높이가 n일 경우 바이너리 트리의 총 노드 수는 2^n -1 개입니다.

위의 예는, 높이가 3일 때 노드가 총 7개 , 이것은 2^3 -1과 같습니다.

따라서 fib(n) 의 시간 복잡도는 O(2^n -1 ) = O(2^n)입니다.

피보나치의 경우 작은 문제로 나누었을 때, 

큰문제와 작은 문제가 상호 작용할 수 있기 때문에

메모이제이션을 사용한 DP를 사용하면

O(n)으로 풀 수 있습니다.

TDD를 더해봐야 알겠지만 ... 

이렇게 풀면 제한 시간내에 통과를 할 수 있을지는 의문입니다 ?^^

처음 쓰는거라 어떻게 구성을 해야할 지 잘모르겠네요 ㅎㅎㅎ

앞으로 더 나아지는 모습으로 돌아오겠습니다.

1. 켄트 백 [본문으로]