[Algorithm] 효율적인 피보나치 수열 구하기(DP)

1. 반복문 혹은 재귀함수를 이용하여 같은 문제 해결을 반복함. (재귀는 꼬리 재귀 형식으로 최대한 이용하자)
2. 해결된 문제의 답들을 저장해 둘 자료구조를 준비한다. ArrayList가 인덱스가 존재하여 가장 만만하다.
3. 반복문의 심층에서 탈출할 수 있도록 조건을 구성하고 미리 나올 심층 결과를 ArrayList에 넣어 탈출에 추가적으로 이용한다.
4. 심층부터 반복문을 탈출하며 ArrayList에 답을 저장해간다.

 

아래 코드의 시간 복잡도는 O(n)이 된다.

(재귀함수를 이용한 기본 피보나치 함수는 O(2^n)이다.)

 

public class Solution {
	public int fibonacci(int num) {
    //구한 값을 저장해둘 List 생성
    ArrayList<Integer> remember = new ArrayList<>();
    remember.add(0);
    remember.add(1);
    //피보나치의 0번째와 1번째는 특수하게 따로 저장.
    //재귀호출을 하며 값이 저장된 List와 피보나치 인덱스를 같이 보냄.
    return aux(remember, idx);
  }
	
  public int aux(ArrayList<Integer> remember, int idx) {
    //엔드포인트 설정
    if (remember.size() <= idx) {
      remember.add(aux(remember, idx - 1) + aux(remember, idx - 2));
    }
    //재귀 함수 탈출에 remember(0)와 remember(1)을 이용하는 방법
    return remember.get(idx);
  }
}