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

안녕하세요 뚜디 입니다:)

코딩테스트 연습 - 피보나치 수 | 프로그래머스 (programmers.co.kr)

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

< 프로그래머스 - 피보나치 수 (LV2) >

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

1. 연습 문제

• 문제 설명

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

• 제한 조건

n은 2 이상 100,000 이하인 자연수입니다.

• 입출력 예

n	return
3	2
5	5

 

2. 문제 풀이

이번 문제는 풀이과정을 2가지로 설명드리도록 하겠습니다. (하지만, 1개는 오답)

🔶 재귀 함수 풀이
1. 임의의 정수 n을 입력 받았을때, F(0) = 0, F(1) = 1 이므로 조건문을 선언해준다.
2. 그외 F(2)이상 일경우 재귀 함수를 통해 반복해준다.
=> 솔직히 이과정으로 풀리기는 하는데 결과에서 보시는것처럼 7번부터 런타임 에러 발생한다.
 런타임 에러가 발생하는 정확한 이유를 모르겠다. 추측으로는 바로 진행하지않고 메모리상에
 처리할 데이터를 쌓아놓고있다가 순차적으로 처리가 되어 임의의 정수 n이 큰 수 일경우
 런타임 에러가 발생하는거 같은데 추측일 뿐이다.

🔶 반복문 풀이
1. 임의의 정수 n을 입력 받았을때, F(0) = 0, F(1) = 1, F(2) = 1 이므로 임의의 벡터 temp를 초기화 한다.
2. 반복문을 통해 i = 3 부터 i = n 까지(즉, F(3) 부터 F(n) 까지)의 값을 temp에 저장한다.
3. n까지 반복하여 진행하였다면 temp 마지막 인자값이 피보나치 n의 수가 되므로 리턴한다.

학부생 공부 할때, 재귀 함수를 제대로 할 줄 몰라 반복문으로 재귀 관련 문제를 많이 풀며,
교수님에게 잔소리를 무지들었었는데, 이렇게 써먹게 될줄은 몰랐네요...(아직도 재귀 어려움)

추가 수정 사항 : 동적 계획법 Dynamic Programming(DP) 기법

피보나치 수열을 재귀로 풀었을때 문제가 발생하는 이유를 찾았습니다.

[C++] 동적 계획법 Dynamic Programming(DP) 사용법 (tistory.com)

[C++] 동적 계획법 Dynamic Programming(DP) 사용법

 

3. 소스 코드

• 재귀 함수 ( 체점 결과 : 실패 )

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

using namespace std;

int solution(int n) {
    int answer = 0;

    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return (solution(n - 1) + solution(n - 2)) % 1234567;
    }

    return answer;
}

• 반복문 ( 채점 결과 : 성공)

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

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> temp = { 0, 1, 1 };

    for (int i = 3; i <= n; i++) {
        temp.push_back((temp[i - 1] + temp[i - 2]) % 1234567);
    }  
    answer = temp.back();

    return answer;
}

 

4. 결과

• 재귀 함수

• 반복문