피보나치 수

🔗 문제 링크

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

❔ 문제 설명

피보나치 수는 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은 1이상, 100000이하인 자연수입니다.

---

💡 풀이 (사용언어 : Java)

처음에 재귀함수를 이용해서 풀었지만 시간초과 판정을 받아서 배열로 메모이제이션 기법을 이용한 알고리즘을 작성했다. 재귀함수는 간결하지만 함수 호출이 많아 스택이 다 차서 문제가 생기거나, 계산을 거듭할수록 계산 속도가 느려진다고 한다. 아래 방법은 해당 타겟 피보나치 수까지 구하는데 필요한 수를 모두 구한다. 처음 순서의 수부터 피보나치 수를 구해서 배열에 저장해주고 그것을 이용해 다음 피보나치 수를 구하는 코드이다.

class Solution {
    private int fibo(int num) {
        // 각 수의 피보나치 숫자를 담아줄 배열 선언
        int[] fiboArr = new int[num + 1];
        // 0과 1의 경우 초기화
        fiboArr[0] = 0; fiboArr[1] = 1;
        // 0과 1의 경우
        if (num < 2)
            return fiboArr[num];
        // 그 앞의 배열의 피보나치 수를 이용해서 피보나치 수를 구해 배열에 기록
        else {
            for (int i = 2; i < num; i++)
                fiboArr[i] = (fiboArr[i-1] + fiboArr[i-2]) % 1234567;
        }
        return (fiboArr[num - 1] + fiboArr[num - 2]) % 1234567;
    }

    public int solution(int n) {
        return fibo(n);
    }
}