[Python, Java] 프로그래머스 - 피보나치수

문제

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

 

피보나치 방법의 기초인 재귀 호출을 통해 시도해보았습니다.

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def solution(n):
    answer = fibonacci(n)
    return answer % 1234567

런타임 에러가 발생했는데, 아마 재귀호출의 깊이 제한 때문에 발생했다고 생각이 듭니다. 재귀 호출에는 깊이 제한을 두고 있고 이 제한을 넘어서면 프로그램이 안전하게 실행 될 수 없기 때문에 에러를 반환합니다. 이 에러가 Recursion Error이고 파이썬에서의 기본 재귀 깊이 한도는 약 1000입니다. n이 100,000까지 커질 수 있기 때문에 테스트 케이스에서 통과를 하더라도 다른 테스트 케이스에서 오류가 발생할 수 있습니다. 마찬가지로 자바에서도 StackOverFlowError가 발생할 수 있습니다.

풀이

1. fib 배열을 통해 이전 결과를 저장하여 중복 계산을 피합니다
2. 2부터 n까지 한번만 수행하면 되기 때문에 O(n)의 시간 복잡도를 가집니다.

Java

class Solution {
    public int solution(int n) {
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++) { // 조건 수정
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        return fib[n];
    }
}

Python

def solution(n):
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567
    return fib[n]

 

문제가 간단한 만큼 다른 풀이를 둘러보았을 때 비슷비슷했지만 그래도 다른 방식인 DP로도 풀어보겠습니당 

1. a, b, c는 피보나치 수열의 이전 두 값(a, b)과 현재 계산된 값을 저장하는 변수입니다.
2. a와 b는 피보나치 수열의 첫 번째 두 값을 의미합니다:
   • a = 0 (F(0))
   • b = 1 (F(1))
3. c는 계산된 값을 임시로 저장하기 위한 변수입니다.
4. range(2, n+1):
   • 반복문은 피보나치 수열의 두 번째 항(F(2))부터 F(n)까지 계산합니다.

• c = (a + b) % 1234567:
  • 현재 피보나치 항(F(i))를 계산합니다: F(i)=F(i−1)+F(i−2)
  • F(i)=F(i−1)+F(i−2)F(i) = F(i-1) + F(i-2)
  • 계산 결과를 1234567로 나눈 나머지를 저장합니다. 이를 통해 값이 커지는 것을 방지하고 효율적인 연산을 유지합니다.
• a = b와 b = c:
  • 피보나치 수열의 다음 항을 계산하기 위해 이전 값들을 업데이트합니다:
    • a는 현재 b의 값으로 업데이트 (즉, F(i-1)).
    • b는 현재 계산된 c의 값으로 업데이트 (즉, F(i)).

Java

class Solution {
    public int solution(int n) {
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % 1234567;
            a = b;
            b = c;
        }
        return b;
    }
}

Python

def solution(n):
    a = 0
    b = 1
    c = 0
    for i in range(2,n+1):
        c = (a+b) % 1234567
        a = b
        b = c
    return b