2748번 : 피보나치 수 2

문제 : 백준 2748번 - 피보나치 수 2

---

1. 풀이

1) 시간 복잡도 : O(1)..?

2) 완전탐색 : 가능은 하지만..DP로 접근할 수 있는 증거가 있다!

• 큰 문제를 작은 문제로 분할할 수 있다!
• 재귀 느낌이 난다..!

3) 작성

""""
1) 문제 정의 : 피보나치 수열에서 n번째 숫자 구하기!
2) 조건
- 입력 : n (n번째)
- 출력 : n번째 피보나치 수

3-1) 로직 (상향식)
- 입력값 n을 받는다.
- n만큼 for문을 돌면서, fibo 메모이제이션을 만든다.
- n번째 값을 출력한다.

3-2) 로직 (하향식)
- 입력값 n을 받는다.
- 빈 타뷸레이션 fibo를 전역으로 만들어 놓는다.
- 재귀를 사용하여 n번째 수를 찾아낸다.
  - 함수 매개변수 : n / 출력 : fibo[n]
  - 종료 조건 : n == 0/1인 경우 -> 0/1을 리턴
               fibo[n]이 있는 경우 -> fibo[n]을 리턴
  - 재귀 조건 : return fibo(n-1) + fibo(n-2)
- 반환받은 값(n번째 수)를 출력한다.
"""

# 상향식
import sys
input = sys.stdin.readline

n = int(input().strip())

fibo = [-1] * (n+1)
fibo[0] = 0
fibo[1] = 1

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

print(fibo[n])

# 하향식
import sys
input = sys.stdin.readline

n = int(input().strip())

fibo = [-1] * (n+1)
fibo[0] = 0
fibo[1] = 1

def recurFibo(n):
    global fibo
    if n == 0 or n == 1 or fibo[n] != -1:
        return fibo[n]
    
    return recurFibo(n-1) + recurFibo(n-2)

print(recurFibo(n))

• 소요 시간 : 39분

• 막힌 부분 :

  • 1차 - 런타임 에러 ⇒ 리스트 원소 할당 헷갈림
    
  • 2차 - 시간 초과 (하향식) ⇒ 메모이제이션 사용하지 않음.. (즉, 리스트 원소 할당이 전혀 이뤄지고 있지 않음) ⇒ “메모이제이션은 계산된 값을 저장하여 중복 계산을 피하는 기술입니다.”

    import sys
    input = sys.stdin.readline
    
    n = int(input().strip())
    
    fibo = [-1] * (n+1)
    fibo[0] = 0
    fibo[1] = 1
    
    def recurFibo(n):
        global fibo
        if n == 0 or n == 1 or fibo[n] != -1:
            return fibo[n]
    
        **fibo[n] = recurFibo(n-1) + recurFibo(n-2)**
     
        **return fibo[n]**
    
    print(recurFibo(n))