문제

[코플릿 - fibonacci]

---

naive solution

public int fibonacci(int num) {
   if(num <= 1) return num;
   return fibonacci(num-1) + fibonacci(num-2);
}

• 재귀 사용
• 시간 복잡도 : O(2^N)

동적계획법(Dynamic programming)

• 큰 문제를 작은 문제로 나누어 푸는 문제
  • 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤, 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.
• 간단하게 설명하면, 저장했던 값을 재사용하는 알고리즘!이라고 할 수 있다.
  
  

동적 계획법의 종류

• Top-down: 큰 문제부터 시작해서 계속 작은 문제로 분할해 가면서 푸는 것 => 메모이제이션
  • 재귀 함수를 사용

• Bottom-up: 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것 => 타뷸레이션
  • 모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식
  • 반복문을 사용

메모이제이션/테뷸레이션 : 계산이 필요한 순간 계산해서 저장한다.

Dynamic with Memoization

public int fibonacci(int num) {
    ArrayList<Integer> al = new ArrayList<>();
    al.add(0);
    al.add(1);

    return aux(al, num);
}

public int aux(ArrayList<Integer> memo, int num){ // 재귀
    if(memo.size() <= num){ // memo가 존재하지 않는다면
        memo.add(aux(memo, num-2) + aux(memo, num-1));
    }
    return memo.get(num);
}

Dynamic with Tabulation

public int fibonacci(int num) {
   ArrayList<Integer> al = new ArrayList<>();
   al.add(0);
   al.add(1);
   
   for(int i=2; i<=num; i++){
       al.add(al.get(i-1) + al.get(i-2));
   }
   return al.get(num);
}

• for문을 사용하기 때문에, 재귀(Memoization)보다 연산이 빠르다.

---

[참고]

동적 계획법
메모이제이션/타뷸레이션
메모이제이션/타뷸레이션 - 2
https://miiinnn23.tistory.com/1