*작성 중 ** [알고리즘] 피보나치 - 재귀함수와 동적계획법 알고리즘

피보나치 : fibonacci

피보나치를 JavaScript로 구현을 해보겠습니다.  이왕 하는 김에 시간 복잡도도 고려해보면서 다양한 방식으로 구현해봅시다요. 

 

0   1   1   2   3   5   8   13   21   34   55 ,,,

 

 

     1. 기본 피보나치

function fibonacci(n){
	//0항과 1항은 그대로 0 과 1임
    if(n <= 1){
      return n;
    }

    // 2 이상은 재귀함수를 이용해서 피보나치를 구현합니다. 
    return fibonacci(n-1) + fibonacci(n-2) 
}

재귀함수를 이용하여 피보나치를 구현하면 함수를 두번 호출하는 중복 호출이 많아져 런타임이 길어집니다. 기본 피보나치에서 시간 복잡도는 O(2^n) 입니다. 이는 시간 복잡도가 비효율적임을 의미합니다.

 

*시간복잡도 : 문제를 해결하는데 필요한 시간

 

 

 

 

     2. 동적계획법의 알고리즘 (DP : Dynamic Programming)

큰 문제를 작은 문제로 나누어서 푸는 방식의 알고리즘 

 

이렇게 쪼개진 작은 문제로부터 원래 문제에 대한 답을 계산해 낸다는 점에서 분할 정복(D&C : Divide & Conquer)과 비슷하지만 동적 계획법에서는 쪼개진 작은 문제가 중복되지만 분할 정복은 절대로 중복 될 수가 없다는 차이점이 있습니다. 

 

이미 계산한 값을 저장해 두는 메로리를 캐시(cache) 라고 하며 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다. 

 

 

 

2-1. 반복적 동적 계획법 

Iterative Dynamic Programming

function fibonacci(n) {
  const cache = Array(100 + 1).fill(0)
  //101길이의 배열을 0으로 채우기 
  cache[1] = 1;

  //cache는 새로운 피보나치 배열이 된다. 
  for( let i = 2; i <= 101; i++){
    cache[i] = cache[i-1] + cache[i-2];
  }
  return cache[n];

}

시간복잡도의 효율을 증가시키기 위해 재귀함수를 한 번만 호출하여 구현해보았습니다. 시간 복잡도는 O(n) 으로 매우 효율적입니다 각 부분 문제를 해결 할 때마다 저장하고 필요할 때마다 다시 함수를 실행하는 것이 아니라 저장 된 값을 가져다 쓰는 방법입니다. 

 

 

 

 

# dynamic with meoization 

시간 복잡도 : O(N)

코드스테이츠에서 푼 피보나치는 for문과 while문 사용을 금지했습니다. 이 조건에 맞추어 다시 풀어보겠습니다. 

function fibonacci(n) {
 // 초기 배열 [ 0, 1 ] 에서 시작해서 배열의 요소를 누적 

 let newArr = [0, 1]; //0번째 1번째 요소는 고정시켜두고 
 
  let fib = (n) => { //함수 한개를 선언해주고
    if (newArr[n] !== undefined){ 
      return newArr[n]; 
      //이미 있는 건 그대로 리턴
      // 구현해 놓은 것은 if문으로 그대로 return 함으로써 런타임 초과를 감소
    }
    newArr[n] = fib(n - 1) + fib(n - 2); //없는 건 새로 만들어서 저장!!!*****
    return newArr[n];
  };
  
  return fib(n); 
}

처음부터 입력 받은 값에 따라 무한으로 재귀함수를 실행시키면 런타임이 초과 되는 단점을 보완하기 위해 newArr 함수에 이미 존재하는 값들을 누적 후 return 하여 런타임 초과를 줄일 수 있다. 

 

 

 

2-2. 재귀적 동적 계획법 

recursive dynamic programming

 

 

 

 

 

cache 를 만들고 그 cache에서 부분 문제의 답을 찾고 없으면 직접 계산한다는 정도의 차이.

함수를 계속 호출하는 데 따르는 오버 헤드가 발생하기 대문에 절대적으로는 반복적 동적 계획법 풀이에 비해 시간이 오래 걸린다. 하지만 둘 다 시간 복잡도는 동일하게 O(n) 이므로 효율에 있어 극적인 차이가 발생하지는 않는다. 

 

 

 

 

 

     3. 결론

반복적 동적 계획법은 비슷하지만 반복문을 이용하여 부분 문제를 순차적으로 해결하면서 전체 문제의 최적해를 구하는 방식. 재귀적으로 호출되는 함수들의 호출 스텍이 필요없기 때문에 메모리 사용량이 더 적습니다. 재귀적 호출 대신 반복문을 사용하기 때문에 함수 호출의 오버헤드를 피할 수 있어 실행 속도가 더 빠릅니다. 

 

* 그래프 알고리즘 : 최단 경로 문제, 최소 스패닝 트리 문제 등 그래프 이론과 관련된 문제 

* 문자열 문제 : 최장 공통 부분 문자열 LCS / 최장 공통 부분 수열 LCIS등 문자열 문제에서 쓰임 

* 행렬 문제 : 행렬 최소 곱셈 문제, 행렬 경로 문제 등 

* 게임 이론 : 게임 이론에서 최적 전략을 찾는 등 다양한 문제에서 쓰임

* 로봇 이동 문제 : 로봇의 이동 경로를 최적화하는 문제 

 

재귀적 동적 계획법은 문제를 작은 부분 문제들로 나누고, 이러한 부분 문제들을 해결하여 전체 문제의 최적해를 구하는 방식. 이때 중복되는 부분 문제들이 많이 발생하기 때문에, 메모이제이션 기법을 사용하여 중복 계산을 피합니다. 

 

* 문자열, 그래프, 행렬 등 다양한 자료 구조와 관련된 문제들에  적용 가능 

* 최적화 문제, 탐색 문제, 결정 문제 등 다양한 유형 다룰 수 있음 

* 피보나치 수열, 최장 공통 부분 문자열(LCS), 최장 증가 부분 수열 (LIS), 행렬 경로 문제, 그리드 월드 문제 등 다양한 문제에서 적용. 

* 컴퓨터 비전, 자연어 처리, 음성 인식 등의 분야에서도 많이 사용 

* 배낭 문제 : 물건을 가방에 넣는 문제 

* 경로 문제 : 미로 차기, 격자상의 경로 문제 등 경로 탐색

* 트리 구조 문제 : 이진 탐색 트리, 트리의 지름 등 

 

 

 

보통 2-1 .반복적 동적 계획법이 더 효율적이로 많이 사용됩니다. 

 

 

 

 

 

 

 

 

 

# 참고 : 동적 계획법 블로그

# 참고 : 피보나치 수열 알고리즘을 해결하는 5가지 방법 (파이썬)

# 참고 : 자바스크립트로 피보나치 수열 효율적으로 구현하기