[프로그래머스]Lv2. 피보나치 수

본 페이지는 C++ 독학을 위해 작성한 포스트입니다 풀이과정도 포함되어있지만 문법공부에 대한 비중이 있습니다.
(+  Java언어 내용도 포함되어있습니다. )

 

 

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

프로그래머스

 

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 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F(4) = F(2) + F(3) = 1 + 2 = 3F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
n은 2 이상 100,000 이하인 자연수입니다.

 

2. 문제해결 접근

• 피보나치 수는,  F(0) = 0, F(1) = 1일 때, 
• 구하고자 하는 앞앞수와 앞수의 합으로 이어진다.
• n번째 수를 구하고자할 때, n번의 연산이 이루어지므로
• 반복문을 통해 조건을 n회 반복되도록 지정하고
• 배열로 지정하여 해당 값이 저장되도록 한다.

 

3.답안 : [언어 : java]

배열로 지정해서 풀이해본다 - 오답

class Solution {
    public int solution(int n) {
    	// 수가 기하급수적으로 늘어나므로 long타입으로 배열을 선언한다.
        long[] arr = new long[n+1];
		arr[0] = 0;
		arr[1] = 1;
 		
		
		//피보나치 수열은 n번째의 수를 구하고자 할때, 앞의 수와 앞앞의 수의 합연산이 이루어진다.
        		
		// i가 0 일때, 0번 인덱스와 1번인덱스의 합이 2인덱스가 되고, 
		// i가 1 일때, 1번 인덱스와 2번인덱스의 합이 3인덱스가 되고, 
		// i가 2 일때, 2번 인덱스와 3번인덱스의 합이 4인덱스가 되고, 
		// i가 3 일때, 3번 인덱스와 4번인덱스의 합이 5인덱스가 되고, 
		// i가 4 일때, 4번 인덱스와 5번인덱스의 합이 6인덱스가 되고, 
        
        // 결과적으로 n번째의 수는 n번의 연산으로 이뤄진다.
        
		for (int i = 2; i <= n; i++) {
			arr[i] = arr[i-1] + arr[i-2];
		}
		
        return (int)arr[n] % 1234567;
    }
}

특정 조건에서 실패

재귀함수를 사용할경우에는 연산이 반복될수록 많은 메모리를 차지하는 단점으로

제대로 연산이 되지 않는것을 확인했다.

 

import java.util.*;

class Solution {
    public int solution(int n) {
         int answer = 0;
		 // n은 2 이상의 수가 인자로 들어오지만, 연산오류를 방지하기 위해 2을 리턴한다
		 if(n == 1 || n == 0) return 2;
		 int a = 0;		// 앞앞수
		 int b = 1;		// 앞수
		 
		 //n번째수는 앞앞수 a와, 앞수 b의 합을 1234567로 나눈 나머지 값을 갖는다.
		 for (int i = 2; i <= n; i++) {
			answer = (a+b) % 1234567;
			
            //값을 재정의
			a = b;
			b = answer;
		}
		 
		 return answer;
    }
}

 

 

4. C++ 답안

#include <string>
#include <vector>

using namespace std;

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

 

C++  문법도 크게 다를것은 없다