프로그래머스 : 피보나치 수 [C++]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12945

 

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

문제 입출력 예)

n	return
3	2
5	5

 

문제 풀이1

• 피보나치 수열 함수를 만들어서, 실행해 주도록 한다.

1. 피보나치 수열 함수 작성
2. 나머지연산자 이용

#include <string>
#include <vector>
#include <iostream>
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) {
    int answer = fibo(n) % 1234567;
    return answer;
}

 

엥?? 이게 왠일인지

시간 초과로 피보나치 수열이 실패했다.

재귀함수로 이용할 경우, 높은 수를 계산하게 되면 많은 시간이 소요되었다.

시간복잡도 공부를 더 해야겠다,,...

 

문제 풀이2

• 함수를 사용시, 실행 초과로 테스트를 통과하지 못했다.

1. 배열로 피보나치 수 작성 후 제출

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

int solution(int n) {
    int F[100001];
    F[0] = 0;
    F[1] = 1;
    for(int i=2; i<=n; i++){
        F[i] = (F[i-1] + F[i-2]) % 1234567;
    }
    return F[n];
}

 

리뷰

• 피보나치 수열은 간단하면서, 중요한 내용인 것 같당
• algorithm 시간 복잡도 공부를 해야겠다,,,
• 프로그램에 있어서 시간복잡도가 중요한지 느꼈다..