[백준] 피보나치 수 2

문제보기 - https://www.acmicpc.net/problem/2748

문제명    - 피보나치 수 2

난이도    - B1

문제유형 - DP

풀이일자 - 25.03.11

 

📌 문제 탐색하기

• 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1
• 2번째 부터는 바로 앞 두 피보나치 수의 합이 됨.
• n번째 피보나치 수를 출력해야함.
  • n ≤ 90

 

🛠 시간복잡도 확인

• DP 활용하여 O(n)에 해결가능

 

📌 코드 설계하기

1. n 입력받기
   • int(input()) 활용
2. 초기값 0, 1 이후로 반복문 적용하기
   • for _ in range(2, n + 1) 활용
3. n번째 피보나치 수 출력하기

 

📌 정답 코드(1회차)

# 1. n 입력받기
n = int(input())

# 2. 초기값 0, 1 이후로 반복문 적용하기
a, b = 0, 1
for _ in range(2, n+1):
    a, b = b, a + b
# 3. n번째 피보나치 수 출력하기
print(b)

 

 

 

📌 추가정리

비교 항목	재귀 (Recursion)	동적 계획법 (DP)
해결 방식	자기 자신을 호출	중복 계산을 줄이기 위해 저장
중복 계산	많음 (비효율적)	적음 (효율적)
사용 기법	분할 정복	메모이제이션 또는 반복문
성능	느릴 수 있음 (O(2ⁿ) 예제도 있음)	빠름 (보통 O(n) 정도로 개선 가능)

• DP는 "중복을 제거한 재귀"라고 생각하면 됨!