[PCCP] Lv2: 피보나치수(12945) 해설

문제

- 문제 링크: 피보나치수

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    int a = 0, b = 1, tmp;
    for (int i = 1; i <= n; i++)
    {
        tmp = a;
        a = b;
        b = (tmp + b) % 1234567;
    }
    answer = a;
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 피보나치 문제에서 구할 N번째 항

- N번째 피보나치 수를 구할 때까지 반복문은 N번 수행: O(N)

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i <= n; ++i) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
        }
        return fibo[n];
    }
}

solution 2)

class Solution {
       public int solution(int n) {
        int answer = 0;

        int num1 = 1;
        int num2 = 1;
        
        if(n==1 || n==2) return 1;
        else {
            for(int i=3; i<=n; i++) {
                answer = (num1+num2)%1234567;
                num1 = num2;//전전수
                num2 = answer;//전수
                
            }
            return answer;
        }
    }
}

solution 3)

#include<>

 

(Python)

solution 1)

- N: 구할 N번째 항

- N번째 피보나치 수를 구할 때까지 반복문은 N번 수행: O(N)

def solution(n):
    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append((fib[i - 1] + fib[i - 2]) % 1234567)
    return fib[n]

solution 2)

def solution(n):
    answer = 0
    a, b = 0, 1
    for _ in range(n):
        a, b = b, (a+b)%1234567
    answer = a
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: 피보나치의 문제에서 구할 N번째 항

- N번째 피보나치 수를 구할 때까지 반복문은 N번 수행: O(N)

function solution(n) {
    const fib = [0, 1]
    for (let i = 2; i <= n; ++i) {
        fib.push((fib[i - 1] + fib[i - 2]) % 1234567);
    }
    return fib[n];
}

solution 2)

function solution(n) {
    const divider = 1234567;
    const dp = [0, 1];
    for( let i = 2; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % divider
    }
    return dp[n];
}

solution 3)

import