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

[73] 피보나치 수

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 72%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: DP, 피보나치, 점화식, 모듈러
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12945

문제를 읽을 때 체크할 포인트

전형적인 점화식 문제다. f(n)=f(n-1)+f(n-2)를 그대로 쓰되, 큰 수를 막기 위해 매 단계에서 모듈러를 취하면 된다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. dp[0], dp[1]을 초기화한다.
2. 2부터 n까지 점화식으로 채운다.
3. 마지막 값을 반환한다.

구현할 때 놓치기 쉬운 부분

재귀만으로 풀면 같은 값을 반복해서 계산하게 된다. 이미 구한 피보나치 값을 저장해 두거나, 작은 값부터 차례대로 채우는 구조가 필요하다.

파이썬 정답 코드

def solution(n):
  # dp[0], dp[1]을 초기화한다.
  if n < 2:
    return n

  MOD = 1234567
  a, b = 0, 1
  # 2부터 n까지 점화식으로 채운다.
  for _ in range(2, n + 1):
    a, b = b, (a + b) % MOD
  # 마지막 값을 반환한다.
  return b

시간 복잡도

N은 구하려는 피보나치 인덱스 n이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.