23번

재귀 때 학습했던 피보나치 수열을 구현하는 문제였다.

예전 학습했던 기억을 살려 num=0, num=1일 때를 각각 0,1로 정의하고 fibo(num-1)+fibo(num-2)를 리턴해주어 문제를 풀었으나, 실행 시간 초과가 떴다. Advanced에 '피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재'라는 말이 있었는데 이게 그 이유인 것 같다.

따라서, 기본적인 재귀풀이보다 더 효율적인 방법이 있는 지 찾아보니 메모이제이션 (memoization)이라는 방법을 찾았다.
기존 풀이는 시간복잡도가 0(2^N)으로, 중복적 계산이 이루어지면서 스택프레임을 사용하기 때문에 시간이 오래 걸리고 비효율적이라는 것이다.
이를 보완하는 메모이제이션 방법은 계산을 하면서 메모를 해둬, 이미 계산한 값은 메모해둔 곳에서 가지고 와서 계산하자라는 방법이다.

따라서, 메모를 해둘 ArrayList배열을 선언하고, 우선 확정적인 0과 1의 값을 담아준다.
그 후 memo와 num을 파라미터로 갖는 int타입 함수를 선언해, memo의 크기가 num보다 작거나 같을 때까지 재귀를 돌려주면 되겠다.

이론적으로는 이해가 가는데, 코드 구조가 잘 이해가 가질 않아 시간을 많이 뺏겼다 😅 정규 수업이 끝난 후 다시 한 번 공부해봐야겠다.