백준 1003번 피보나치 함수 - python

문제링크

📌 알고리즘 분류: 동적 프로그래밍 (DP), 수학
📦 핵심 개념: 메모이제이션 (Memoization), 피보나치 수열
🎯 난이도: 실버 3 (백준 기준)

📌 문제 설명

재귀 호출을 통해 피보나치 수를 구할 때, fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지 구하는 문제이다.

재귀로 구현할 경우 비효율적이기 때문에, 동적 프로그래밍(DP) 방식으로 해결하는 것이 핵심

🧩 아이디어

• fibonacci(0)이 호출되는 횟수와
  fibonacci(1)이 호출되는 횟수를 각각 기록해야 한다.

• 예를 들어,
  fibonacci(3) = fibonacci(2) + fibonacci(1)
  이때 호출 횟수도 누적됩니다.

• 따라서 DP 배열을 두 개 만들어 호출 횟수를 저장합니다:
  - zero[n]: fibonacci(n) 호출 시 0이 호출되는 횟수
  - one[n]: fibonacci(n) 호출 시 1이 호출되는 횟수

내 풀이 코드

t = int(input())
zero = [0] * 41
one = [0] * 41

# 초기값 설정
zero[0] = 1
one[1] = 1

# DP를 통해 호출 횟수 누적
for i in range(2, 41):
    zero[i] = zero[i-1] + zero[i-2]
    one[i] = one[i-1] + one[i-2]

# 테스트 케이스 처리
for _ in range(t):
    n = int(input())
    print(zero[n], one[n])

코드 설명

zero = [0] * 41
one = [0] * 41

• 0 ≤ n ≤ 40이므로 0부터 40까지의 호출 횟수를 저장할 배열을 만든다.
• zero[i]: fibonacci(i) 호출 시 0이 출력되는 횟수
• one[i]: fibonacci(i) 호출 시 1이 출력되는 횟수

zero[0] = 1
one[1] = 1

• 문제에 주어진 기저 조건.
• fibonacci(0)은 0만 출력 → zero[0] = 1
• fibonacci(1)은 1만 출력 → one[1] = 1

for i in range(2, 41):
    zero[i] = zero[i-1] + zero[i-2]
    one[i] = one[i-1] + one[i-2]

• 피보나치처럼 DP 배열을 채워가는 과정.
• fibonacci(n)을 호출하면 fibonacci(n-1)과 fibonacci(n-2)를 각각 호출하므로,
• 0의 출력 횟수는: zero[n-1] + zero[n-2]
• 1의 출력 횟수도 마찬가지.

for _ in range(t):
    n = int(input())
    print(zero[n], one[n])

• 테스트 케이스만큼 입력을 받아, 미리 저장해둔 호출 횟수 값을 출력한다.

다른 사람의 풀이

T = int(input())
for _ in range(T):
    N = int(input())
    a, b = 1, 0 # 0과 1이 호출된 횟수
    for i in range(N):
        # 0은 1이 호출된 횟수만큼, 1은 0과 1이 호출된 합만큼 출력됨
        a,b = b, a+b 
    print(a,b)

출처: https://edder773.tistory.com/64 [개발하는 차리의 학습 일기:티스토리]