[프로그래머스] 피보나치 수 / 재귀함수, 반복문

문제

풀이 1(재귀 함수)

#include <string>
#include <vector>

using namespace std;

int fibo(int n){
    if(n==0) return 0;
    else if(n==1) return 1;
    else {
        return fibo(n-1) + fibo(n-2);
    }
}

int solution(int n) {
    return fibo(n)% 1234567;
}

재귀 함수를 이용하여 문제를 풀 경우 일부 문제에서는 런타임 에러가 발생한다.

 

재귀 함수

장점

-변수를 여럿 만들거나 반복문을 사용하지 않아 상대적으로 코드가 간결하다

단점

-지속적으로 함수를 호출하게 되어 반복문에 비해 메모리를 더 많이 사용한다

-메모리를 많이 사용하여 속도 저하로 이어진다.

 

런타임 에러가 났던 이유는 재귀 함수의 깊이에는 한계가 있기 때문이다.

따라서 일부 큰 숫자가 n으로 들어올 경우, 깊이를 초과했기 때문에 에러가 발생한 것이었다!

 

 

 

풀이 2(반복문)

#include <string>
#include <vector>

using namespace std;


int solution(int n) {
    int answer = 0;
    vector<int> vec(n+1,0);
    vec[1] = 1;
    for(int i= 2; i<=n; i++){
        vec[i] = vec[i-1]% 1234567+ vec[i-2]% 1234567;
    }
    return vec[n] % 1234567;
}

vec [i] = vec [i-1]% 1234567+ vec [i-2]% 1234567; 

 

조금만 숫자가 커져도 피보나치는 int로 표현할 수 있는 범위를 넘겨버리는데(-2,147,483,648 ~ 2,147,483,647),

n번째 피보나치 수라고 구한 숫자가, 이미 int의 범위를 넘긴 상태라면 값이 예상치 못한 이상한 결과를 가지게 되고, 이것을 1234567로 나눈다고 한들 정확한 값을 구하는 것은 불가능하기 때문이다. 

 

매번 1234567로 나눈 나머지 값을 사용한 이유는, int의 자료형의 범위를 넘지 않기 위함이며, 밑의 공식이 성립하기 때문이다. 

 

(A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다.

 

 

 

 

---

 

 

다른 사람 풀이

#include<iostream>
#include<vector>
using namespace std;

typedef vector<vector<long long>> matrix;

matrix operator* (matrix &a, matrix &b) {
  int n = a.size();
  matrix c(n, vector<long long>(n));
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      for(int k=0; k<n; k++)
        c[i][j] += a[i][k] * b[k][j];
  return c;
}

long long fibonacci(int n)
{
  matrix res = {{1, 0},{0, 1}};
  matrix fib = {{1, 1},{1, 0}};
  while(n) {
    if(n%2==1) res = res * fib;
    fib = fib * fib;
    n *= 0.5;
  }
  return res[0][1];
}

int main()
{
    int testCase = 10;
    long long testAnswer = fibonacci(testCase);

    cout<<testAnswer;
}

효율이 좋은 코드라고는 하는데 이해하기가 좀 힘들다.

좀 더 공부를 하고 다시 리뷰해야 할 듯하다.

 

 

---

 

 

https://jireh.tistory.com/14

[프로그래머스] 만만할 줄 알았던 피보나치 수 JS

https://programmers.co.kr/questions/11991

프로그래머스