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

1. 문제이해

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

코딩테스트 연습 - 피보나치 수

 

N번째 피보나치 수를 1234567로 나눈 나머지 값을 리턴하는 것이 목표이다.

 

 

 

2. 문제풀이

 

주어진 N에 대해 N번째 피보나치 수를 구하고, 이를 1234567로 나눈 나머지 값을 구해야 한다.

피보나치 수열이란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로,

0번째부터 시작해, 0, 1, 1, 2, 3, 5 ... 와 같은 규칙을 띈다.

 

문제는 간단해보이나, 주의해야할 점이 하나있다.바로 시간초과이다.

 

 

나는 먼저 재귀를 통해 피보나치 수열을 구현했는데,

재귀를 통해 구현한 결과, 7번째부터 위와 같은 시간초과로 인한 실패를 마주하게 되었다.

재귀를 통해 구현하면 비교적 시간이 오래걸리기 때문에,

재귀 대신 for문을 사용함으로써, 시간초과를 해결해주었다.

(시간초과가 난 재귀함수를 통해 구현한 코드도 아래에 같이 첨부했다.)

 

문제의 주어진 틀은 아래와 같았다.

 

 

 

 

3. 소스코드

1. 재귀를 통해 구현한 코드 (시간초과(실패))

#include <string>
#include <vector>

using namespace std;

int fibonacci(int fn){
    if(fn == 0) {	// 0인 경우
        return 0;
    }
    
    if(fn ==1) {	// 1인 경우
        return 1;
    }
    
    if(fn >= 2) {	// 2 이상인 경우부터는
    	// 재귀함수 적용
        return fibonacci(fn-1) + fibonacci(fn-2);
    }
}

int solution(int n) {
    int answer = 0;
    
    answer = fibonacci(n) % 1234567;
    
    return answer;
}

위 코드는 비록 시간초과로 실패한 코드이지만,

재귀를 통해 피보나치 수열을 구현한 코드이다.

부끄럽지만, 이 또한 하나의 과정이라고 생각하고 올려본다.😤

 

 

2. for문을 통해 구현한 코드 (성공)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int fibonacci[100000];   // 수열의 크기는 임의로 100000으로 정했다.
    
    fibonacci[0] = 0;   // 0번째 피보나치 수
    fibonacci[1] = 1;   // 1번째 피보나치 수
    
    for(int i = 2; i <= n; i++) {   // 2부터 주어진 N까지 연산시작
        fibonacci[i] = (fibonacci[i-1] + fibonacci[i-2]) % 1234567;
    }
    
    answer = fibonacci[n];
    
    return answer;
}

수열의 크기는 따로 명시된 것이 없어 임의로 크게 설정했다.

(10000으로 설정했더니, 테스트 13, 14에서 segmantation fault가 발생했다.)

 

우선, 0번째와 1번째 피보나치 수를 설정한 뒤,

2번째 피보나치 수부터는 이전 수 두개의 값을 더해나가며 피보나치 수열을 생성해나갔다.

또한, 1234567로 나누어진 나머지값을 구해야 하기때문에,

피보나치 연산과 동시에 해당 값으로 나눈 나머지 값을 수열에 넣어주었다.

 

여기서 한 가지 더 주의할 점은, 연산과 동시에 나머지 값을 구해야 한다는 점이다.

피보나치 연산을 모두 끝마친 후 1234567로 나누면, (answer = fibonacci[n] % 1234567)

제대로 된 값을 반환하지 못하고 실패하게 된다.

(아마 int형의 범위를 넘어가게 되면, 수가 바뀌게 되는데,

그 경우, 이미 다른 수로 바뀐 지점에서 나머지 연산을 해주면

다른 결괏값이 나오기 때문인것으로 추정된다.)

정확한 답변을 알고계신 분이 계시다면 댓글 부탁드립니다.🙇‍♂️🙇‍♀️

 

 

---

피보나치 수열은 왜 언제나 날 당황시키는 걸까..

백준에서도 시간초과를 겪었었던 것 같은데..😭😭

다음에는 당황하지 않도록 열심히 단련해야지..💪💪