효율적인 피보나치
피보나치 (fibonacci)
0번째와 1번째에 값으로 0과 1이 주어진다.
그다음 번째는 현재 번째의 뒤의 두 값을 더하는값이 된다. 2번째 = 0번째 + 1번째, 3번째 = 2번째 + 1번째
재귀를 이용한 피보나치
3번째 값의 동작
-> 2번째 + 1번째 (값 1)
-> 2번째 값은
-> 1번째 값 (값 1) + 0번째 값 (값 0) = 값(1)
-> 2번째 (값 1) + 1번째 (값 1) = (값 2)
4번째 값의 동작
-> 3번째 + 2번째
-> 3번째 값은
-> 2번째 + 1번째 (값 1)
-> 2번째 값은
-> 1번째 값 (값 1) + 0번째 값 (값 0) = 값(1)
-> 2번째 (값 1) + 1번째 (값 1) = (값 2)
-> 2번째 값은
-> 1번째 값 (값 1) + 0번째 값 (값 0) = 값(1)
-> 3번째 (값 2) + 2번째 (값 1) = (값 3)
이 경우 시간복잡도는
시간 복잡도를 줄이려면 어떻게 해야 될까?
재귀함수를 살펴보면
코드는 순서대로 흘러간다 fibonacci(num-1) 을 먼저 수행하고 그 다음 fibonacci(num-2)가 수행이 된다.
5번째 값을 구할 때 4번째하고 3번째를 더하게 되고 4번째를 먼저 구하면서 3번째 값을 알 수 가있지만 위의 코드에서는 4번째값을 쭉 구하고 또 3번째 값을 쭉 구하고 있다.
결론 = 3번째 값이 저장되 있으면 굳이 한 번 더 작업을 안해도 된다.
효율적인 fibonacci
8의 값을 구할 때
위의 식을 보면 memo.size()가 2이고 num이 8이기 때문에 if문으로 들어와 먼저 memo.add()를 수행하고 그 중에서
aux(memo, 7) + aux(memo, 6) 을 진행하게 되지만 코드 순서에 맞게 aux(memo, 7) 과정을 먼저 재귀함수가 수행된다.
aux(memo, 7) 재귀함수가 끝나게 되면
그리고 aux(memo, 6) 을 수행한다.
if( memo.size() <= num) 이 성립이 되지 않는다. 이미 memo에 7번째 값까지 구해놨기 때문에 6번째는 이미 존재.
그렇기에 따로 재귀함수를 돌지 않고 6번째 값인 8을 리턴한다.
아까 말했던 n-2 값을 구하지 않기 위하여 ArrayList를 통하여 미리 값을 저장하는 역할을 수행하였다.
최종적으로 aux(memo, 7) + aux(memo, 6) -> 13 + 8 = 21의 결과가 나오게 된다.