1. 문제

---

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2747

2. 아이디어

---

• 1. recursion

  1. n이 1이나 2면 result = 1
  2. 아니면 result = solve1(n-1) + solve1(n-2)로 하는데 이 때 계산량이 많아져서 시간초과

2. Memorized

1. 구한 값을 memo list에 저장하여 다음에 같은 계산을 하지 않고 memo list에 이미 계산된 값을 return한다.

3. Bottom-Up

1. for문을 이용하여 아래부터 n까지 차근차근 계산

👉👉 2, 3번 방법은 필요한 메모리와 처리 속도가 같다. 👈👈

3. 코드

---

clone 1

def solve1(n): # 기본적인 재귀 
  if n == 1 or n == 2:
    result = 1
  else:
    result = solve1(n-1) + solve1(n-2)
  return result

n = int(input())
print(solve1(n))

clone 2

def solve2(n, memo): # memorized
  if memo[n] is not None:
    return memo[n]
  if n == 1 or n == 2:
    result = 1
  else:
    result = solve2(n-1, memo) + solve2(n-2, memo)
  memo[n] = result
  return result

n = int(input())
memo = [None] * (n+1)
print(solve2(n, memo))

clone 3

def solve3(n):
  if n==1 or n == 2:
    return 1
  bottom_up = [None] * (n+1)
  bottom_up[1] = 1
  bottom_up[2] = 1
  for i in range(3, n+1):
    bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
  return bottom_up[n]

n = int(input())
print(solve3(n))

dp의 흐름을 놓치기도 했고 너무 어려워서 다시 차근차근 여러 강의를 들으면서 공부해보겠다.
출처 : https://www.youtube.com/watch?v=vYquumk4nWw