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

피보나치 수

문제 링크

피보나치 수

분석

피보나치 수를 구하는 문제입니다.
피보나치 수를 구할 때 1234567로 나눈 나머지 값을 구해야합니다.

풀이

재귀함수를 통해 구현한 방법입니다.
해당 방법은 시간초과로 실패합니다.
하지만 일반적으로 피보나치 수를 구현하는 방법 중 하나이므로 풀이에 작성했습니다.

int fibonacci(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

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

---

반복문을 사용한 방법입니다.

int solution(int n) {
    int sum = 0;
    int prev1 = 0;
    int prev2 = 1;
    
    for (int i = 2; i <= n; i++)
    {
        sum = (prev1 + prev2) % 1234567;
        prev1 = prev2;
        prev2 = sum;
    }
    
    return prev2;
}

성능 요약

재귀함수를 사용한 성능입니다.

시간 복잡도는 $O(n^2)$입니다.

• fibonacci함수가 재귀함수이며, 2배씩 늘어나므로 $O(n^2)$

공간 복잡도는 $O(n)$입니다.

• fibonacci함수가 재귀함수이므로, 스택 프레임이 쌓입니다. $O(n)$

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.16MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.12MB)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)

---

반복문을 사용한 성능입니다.

시간 복잡도는 $O(n)$입니다.

• n에 대한 반복문 $O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.23MB)
테스트 2 〉 통과 (0.01ms, 4.03MB)
테스트 3 〉 통과 (0.01ms, 3.68MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.17MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.15MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.33ms, 4.21MB)
테스트 14 〉 통과 (0.33ms, 4.14MB)