[Programmers - lv02] 피보나치 수 (cpp / python)

피보나치 수

프로그래머스

문제 설명

피보나치 수를 구해보자.

흔히들 알고있는 점화식 $f(n) = f(n-1) + f(n-2)$ 를 이용하여 문제를 해결한다.

문제 풀이

소스코드 : C++

반복문(dynamic programming - bottom-up: Tabulation)을 이용한 풀이1

#include<iostream>
#include <string>
#include <vector>

using namespace std;
const int MAX = 100001;
const int MOD = 1234567;
int dp[MAX];
int solution(int n) {
    for(int i=0; i<=n; i++){
        if(i<=1) dp[i] = i;
        else dp[i] = (dp[i-1] + dp[i-2])%MOD;
    }
    return dp[n];
}

사실 위 방식은 공간효율성이 떨어진다 반복문을 이용하면 모든 계산 결과를 저장(memoization)할 필요가 없다.

따라서 아래 방식이 더 효율적이다.

 

반복문(dynamic programming - bottom-up: Tabulation)을 이용한 풀이2

#include<iostream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
const int MOD = 1234567;
int solution(int n) {
    int f[3] = {0,1,1};
    for(int i = 3; i <= n; i++) 
        f[i%3] = (f[(i-1)%3] + f[(i-2)%3])%MOD;
  return f[n%3];
}

재귀 함수 를 이용한 풀이 -> 시간초과

#include<iostream>
#include <string>
#include <vector>
#define ll long long

using namespace std;
const int MAX = 100001;
const int MOD = 1234567;
//int dp[MAX];
int solution(int n) {
    if(n<=1)return n;
    else return (solution(n-1) + solution(n-2))%MOD;
}

반복문과 재귀함수의 차이 -Link 에서 포스팅한 것처럼 재귀함수의 성능을 알 수 있다.

이를 해결하려면 Dynamic Programming 을 이용하거나 꼬리 재귀 를 이용하여야한다.

꼬리재귀 를 이용한 풀이

#include<iostream>
#include <string>
#include <vector>

using namespace std;
const int MOD = 1234567;
int process(int pprev, int prev, int n) {
    if(n==0) return pprev;
    else return process(prev, (pprev + prev)%MOD, n-1);
}
int solution(int n){
    return process(0,1,n);
}

Dynamic Programming(Top-dwon: memoization) & 재귀 함수 를 이용한 풀이

#include<iostream>
#include <string>
#include <vector>

using namespace std;
const int MAX = 100001;
const int MOD = 1234567;
int dp[MAX];
int solution(int n) {
    if(n<=1)return dp[n] = n;
    if(dp[n])return dp[n];
    dp[n] = (solution(n-1) + solution(n-2))%MOD;
    return dp[n];
}

Dynamic Programming & 반복문 을 이용한 풀이

반복문1	재귀함수	꼬리재귀	재귀 + memoization	반복문2

반복문과 꼬리재귀는 같은 방식이라고 생각하면된다. 따라서 시간, 공간 복잡도 차이에서 크게 차이나지 않는다.

그리고 따지고 보면 반복문과 꼬리재귀는 이미 DP를 이용한 풀이이다. DP 이란 컴퓨터 언어로 코딩을 한다는 의미가 아니라 일종의 계획을 의미한다.  

따라서 여러가지 DP 기법 중 Memoization을 이미 이용한 풀이이다. Memoization이란 한 번 이루어진 계산을 다시 또 수행하지 않도록 하는 것인데 반복문과 꼬리재귀는 N-1, N-2의 값을 이미 계속해서 저장하며 문제를 해결하고있다. 하지만 재귀함수를 이용한 풀이는 따로 DP를 하지않고 N-1, N-2에 대한 계산이 필요할 때마다 다시 호출하여 문제를 해결하므로 시간초과의 결과가 나오는 것이다.  

1~N까지의 피보나치 수의 결과가 필요할 때에는 Memoization을 1 ~ N을 모두 담을 수 잇는 공간을 할당(반복+DP 풀이)해주면 되는 것이고 그렇지 않다면 필요한 계산과정만 필요하다면 반복문이나 꼬리재귀처럼 공간을 필요만큼만 사용하여 문제를 해결하면 될 것 같다.

마지막으로 위와 같이 점화식 방식이 아닌 행렬 곱 방식으로도 해결할 수 있다.

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

const int MOD = 1234567;
typedef vector<vector<ll>> matrix;

matrix operator*(matrix &a, matrix &b){
    int n = a.size();
    matrix c(n, vector<ll>(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];
            }
            c[i][j] %= MOD;
        }
    }
    return c;
}
ll solution(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 >>= 1;
    }
    return res[0][1];
}

 

소스코드 : Python

파이썬은 반복문(bottom-up) 을 이용하여 해결했다.

def solution(n):
    answer =0
    MOD = 1234567
    dp = [0 for i in range(n+1)]
    for i in range(n+1):
        if i<=1 : dp[i] = i
        elif not dp[i]: dp[i] =(dp[i-1]+dp[i-2])%MOD    
    answer = dp[n]
    return answer

 

 

반복문과 재귀함수에 대해 자세히 알고 싶다면 이전 포스팅을 참고해보세요.

https://wonillism.tistory.com/17

[Algorithm - Theory]반복문과 재귀함수의 차이