2. Fibonacci Sequence( 피보나치 수열 )

아래는 피보나치 수열의 점화식이다.

아래는 프로그램 소스이다.

 

 

프로그램 실행 결과 창

 

아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다.

중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 수열의 4번째 항을 중복으로 구한다.

즉, 이미 알아낸 항의 값을 다시 구하려고 한다.

이에 대한 한 가지 방법은 뒤에서 설명하도록 한다.

 

아래로 이동해서 중복을 제거하는 방법을 알아보자.

designatedroom87.tistory.com/4

3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기