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

피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자.

designatedroom87.tistory.com/3?category=868275

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

 

아래는 memoization 방법을 이용해 피보나치 수열을 구할 알고리즘이다.

앞서, 피보나치 수열을 구할 때, 이미 구한 항의 값을 다시 구하는 것이 문제라 하였는데,

여기서 기록을 통해 이를 해결하고자 한다.

즉, 기록한 항이 있으면 그 값을 리턴하면 되고, 기록하지 않은 새로운 항이라면

이 새로운 항에 대한 수열 값을 구한 뒤에 기록하면 된다.

 

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

아래는 프로그램 결과 창이다.

 

보충 설명을 하면

위의 DT배열은 임시로 256칸으로 할당하는데, 이 배열의 인덱스와 값이 의미하는 것은 아래와 같다.

인덱스는 피보나치 수열의 항을 의미하고, 값은 그 항의 값을 의미한다.

예를 들면, 5번째 인덱스에는 3의 값이 들어있어야 한다.

만약에 5번째 인덱스에 0의 값이 들어있다는 의미는,

아직 5번째 항에 대한 피보나치 수열의 값을 기록하지 못했다는 의미이다. 

그리고 배열의 0번 인덱스는 사용하지 않는다. 그 이유는 인덱스는 항에 대응하는데 0번째 항은 없다.

수열의 항은 자연수로 시작한다.