[Programmers] L2. 피보나치 수 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 fibo[0] = 0, fibo[1] = 1 미리 정의

 

피보나치 수열에서 첫 두 항, 즉 fibo[0] = 0과 fibo[1] = 1은 시작값이자 수열의 정의에 해당하기 때문에 따로 저장한다. 이들은 피보나치 수열을 계산하는 기초가 된다. 이유는 다음과 같다.

• 재귀적 정의 : 피보나치 수열은 F(n) = F(n − 1) + F(n − 2) 로 정의되며, F(0) = 0과 F(1) = 1 이 없으면 이후의 모든 피보나치 수를 계산할 수 없다. fibo[0]과 fibo[1]이 초기화되지 않으면, 재귀적 연산을 시작할 수 없게 된다.

따라서 0과 1은 먼저 따로 저장하고, 2부터 반복문을 돌린다.

Solution

def solution(n):
    fibo = [0]*(n + 1)

    fibo[0] = 0
    fibo[1] = 1
    for i in range(2, n + 1):
        fibo[i] = fibo[i - 1] + fibo[i - 2]

    return fibo[n] % 1234567

 

📌 1234567로 나누는 이유 ?

• 값의 크기 제한
  • 피보나치 수는 순서가 커질수록 매우 빠르게 증가하기 때문에, 큰 숫자를 계산하다 보면 메모리와 연산 시간 모두 부담이 된다. 10^6번째 피보나치 수는 수십만 자리의 수로, 계산과 저장이 어렵다. 따라서 결과를 1234567로 나누어 계산하면 값이 작아져서 더 빠르고 효율적으로 연산할 수 있다.
• 문제의 특성 (모듈러 연산)
  • 많은 문제에서 값이 매우 커질 때는 특정 수로 나눈 나머지를 구하는 방식이 사용된다. 특히 피보나치 수처럼 증가 속도가 매우 빠른 경우 모듈러 연산을 통해 결과의 크기를 조절하는 것은 일반적이다.

따라서 1234567로 나누는 이유는 값의 크기 제한과 모듈러 연산 규칙을 따른 요구사항 때문이다.

 

---