Baekjoon 문제 풀기 (10870번 : 피보나치 수 5) Python

10870번 : 피보나치 수 5

1. 문제읽기

---

대표적인 Dynamic Programming 문제

피보나치 수열 문제는 대표적인 dp 알고리즘 문제이다.
재귀와 dp 메모이제이션을 이용하여 각각 풀 수 있는데,
재귀는 단순하지만 오래걸린다. 이 문제는 입력값이 작지만 오래걸려서 채점하긴 싫으니까 패스했다.

취소선을 그은 이유는 3번을 보면 알 수 있다…

2. 제출 코드

---

재귀를 이용하여 문제를 풀까 하다가 사실 문제에서 요구하는 건 입력 값이 크지 않고 피보나치 수열을 만들어서 출력하기만 하면 되서 for문으로 피보나치 수열을 만들어주고 그냥 그 값을 출력했다.
라고 생각했는데 동빈북을 보니 글쎄 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한종류라고 한다.
나는 재귀와 메모이제이션을 쓰는 것이 다이나믹 프로그래밍의 구현 방법이라고 생각했고 여러 개념들이 혼용되어 사용되어서 엄밀히 말하면 위에 내가 써놓은 말은 조금 맞지 않는 말이다.

n = int(input())
fiboList = [0, 1]

for i in range(2, n+1):  # 2부터 n까지 반복
    fiboList.append(fiboList[i-2] + fiboList[i-1])

print(fiboList[n])

3. 공부할 것

---

Dynamic Programming 소스코드 작성 방법

• Top-down 방식 / 하향식
  • 재귀를 활용한 작성법
  • 메모이제이션(Top-down방식에 국한된 표현) 사용
• Bottom-up 방식 / 상향식
  • 반복문을 이용한 작성법
  • DP 테이블(Bottom-up방식에서 사용되는 결과 저장용 리스트) 사용
  • 이 방법을 권장한다. 전형적인 형태.
• Memoization(메모이제이션) 기법 (= Cashing)
  • 다이나믹 프로그래밍을 구현하는 방법 중 하나
  • 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
  • 다이나믹 프로그래밍과는 별도의 개념

막혔던 것 중 하나는 리스트 크기를 어떻게 정해야할지 감이 안와서였는데, 동빈북을 보니 처음에 아래와 같이 크기를 정해줄 수 있었다.
생소한 개념이라 외워둬야지 라고 생각했는데 역시나 까먹었다.
다시 기억해놓아야겠다.

fiboList = [0] * (n+1)  # n번째 피보나치 수 출력을 위한 리스트 생성

따라서 정리한 개념에 따라 내가 생각하고, 풀었던 방법에 대해 다시 써보자면,
피보나치 수열을 보고 메모이제이션을 생각했고, 처음에는 탑다운 방식으로 문제를 풀어보려고 했으나, 채점이 오래걸릴 것 같아서 보텀업 방식으로 문제를 해결했다.
가 맞는 말일 것이다.