백준 1003 피보나치 함수, 다이나믹 프로그래밍 DP (with 파이썬)

✅ 문제 링크: 백준 1003번 - 피보나치 함수

 

1. 피보나치 수열이란?

 

✅ 개념

 

피보나치 수열은 연속한 두 수의 합이 다음 수가 되는 수열이다.

다음과 같이 정의된다.

 

F(n) = F(n-1) + F(n-2)

 

단, 초기값은

F(0) = 0, \quad F(1) = 1

 

🔹 예제

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

2. 다이나믹 프로그래밍(DP)란?

 

✅ 개념

 

“이미 계산한 값을 저장하여 중복 계산을 방지하는 기법”

• 재사용 가능한 값을 저장하여 빠르게 연산

• 재귀 호출을 최소화하여 성능 개선

• 시간 복잡도를 획기적으로 줄일 수 있음

 

✔ 비효율적인 재귀 호출을 방지하여 연산 속도를 크게 향상시킨다.

 

3. 문제 접근 방식

 

❌ 잘못된 접근 (재귀 방식, 시간 초과 발생)

#시간초과 발생하여 실패한 코드
import sys
T = int(sys.stdin.readline().rstrip())
N = [int(input()) for _ in range(0, T)]

def fibonacci(no):
    if (no == 0):        
        return 0
    elif (no == 1):        
        return 1
    else:
        return fibonacci(no-1) + fibonacci(no-2)
    
for i in range(0, T):
    if N[i] == 0:
        print("1 0") #0인 경우, 초기값 리턴
    else:
        print(str(fibonacci(N[i]-1)) + " " + str(fibonacci(N[i])))

 

✅ 문제점:

• 같은 값을 반복해서 재계산하기 때문에 시간 초과가 발생한다.
• N = 40일 경우, 수십만 번 이상의 중복 계산이 발생하여 연산 속도가 매우 느려짐

4. 다이나믹 프로그래밍(DP) 적용한 풀이

 

✅ 해결 방법

• 메모이제이션 (Memoization): 계산된 값을 저장하여 중복 계산을 방지
• 반복문을 이용한 DP: 재귀 대신 반복문을 사용하여 피보나치 수를 계산
• 0과 1의 호출 횟수를 저장하여 활용

5. 파이썬 코드 (DP 적용)

import sys
T = int(sys.stdin.readline().rstrip())
N = [int(input()) for _ in range(0, T)]

#다이나믹 프로그래밍 적용. 한번 호출된 값은 메모리에 저장. 재호출 안함
def fibonacci(no):
    #매개변수 만큼 0으로 세팅한 리스트 생성
    dnmlst = [0 for _ in range(0,no+1)] 
    dnmlst[0] = 0 # 리스트에 피보나치 수열 0 초기값 세팅
    if (no == 0):
        return "1 0" #매개변수 0인 경우, 초기값 리턴
    elif (no > 0):
        dnmlst[1] = 1 # 리스트에 피보나치 수열 1 초기값 세팅

    #반복문 사용
    for i in range(2, no+1):        
        #저장된 이전값으로 재귀호출
        dnmlst[i] = int(dnmlst[i-1]) + int(dnmlst[i-2])                    
    result = str(dnmlst[no-1]) + " " + str(dnmlst[no])
    return result

for i in range(0, T):
    print(fibonacci(N[i]))

 

6. 코드 설명

 

📌 입력 처리

import sys
T = int(sys.stdin.readline().rstrip())  
N = [int(input()) for _ in range(0, T)]

• sys.stdin.readline()을 사용하여 **테스트 케이스 개수(T)**를 입력받음
• N = [int(input()) for _ in range(0, T)]
• T개의 정수를 입력받아 리스트 N에 저장
• 리스트 N에는 각 테스트 케이스에서 입력받은 N값이 저장됨

📌 다이나믹 프로그래밍을 활용한 피보나치 함수

def fibonacci(no):
    # 매개변수만큼 0으로 초기화된 리스트 생성
    dnmlst = [0 for _ in range(0, no+1)]
    dnmlst[0] = 0  # F(0) = 0
    
    if no == 0:
        return "1 0"  # F(0)일 때, 0이 1번, 1이 0번 출력
    
    elif no > 0:
        dnmlst[1] = 1  # F(1) = 1
    
    # DP를 사용한 반복문
    for i in range(2, no+1):        
        dnmlst[i] = int(dnmlst[i-1]) + int(dnmlst[i-2])  

    # 결과를 문자열 형태로 반환
    result = str(dnmlst[no-1]) + " " + str(dnmlst[no])
    return result

 

✅ 주요 동작

1. dnmlst = [0 for _ in range(0, no+1)]

• 길이가 no+1인 리스트를 만들고, 모든 값을 0으로 초기화
• dnmlst[i]에는 F(i) 값이 저장됨

2. dnmlst[0] = 0, dnmlst[1] = 1 (초기값 설정)

3. for i in range(2, no+1)

• dnmlst[i] = dnmlst[i-1] + dnmlst[i-2]
• 이전 두 개의 값을 더해서 F(i)를 구함 (DP 적용)

4. result = str(dnmlst[no-1]) + " " + str(dnmlst[no])

• 0이 출력된 횟수: dnmlst[no-1]
• 1이 출력된 횟수: dnmlst[no]
• 결과를 문자열 형태로 반환

📌 결과 출력

for i in range(0, T):
    print(fibonacci(N[i]))

• T개의 테스트 케이스에 대해 fibonacci(N[i])를 호출
• 결과를 출력

7. 예제 테스트

 

✔ 입력 예시

3
0
1
3

 

✔ 출력 예시

1 0
0 1
1 2

 

✔ 입력 예시 2

2
6
22

 

✔ 출력 예시 2

5 8
10946 17711

 

8. 시간 복잡도 분석

접근방식	시간 복잡도	문제점
재귀 방식	O(2^N)	중복 호출이 많아 N=40에서 시간 초과
DP 방식	O(N)	0~40까지 미리 계산 후 빠르게 결과 반환

✔ DP 방식을 사용하면 최대 입력값 N=40에서도 매우 빠르게 실행 가능

 

9. 정리

 

✔ 피보나치 수열의 성질을 이용하여 0과 1의 호출 횟수를 구하는 문제

✔ 재귀 방식은 중복 연산이 많아 시간 초과 발생 → DP 방식 사용

✔ DP 배열을 미리 채워 O(N)의 시간 복잡도로 문제 해결 가능