다이나믹 프로그래밍 DP & 백준 피보나치 수열

다이나믹 프로그래밍이란?

- 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

- 작은 문제의 값을 재활용 하여 상당한 시간복잡도를 줄 일 수 있다

- 대신 메모리를 사용하여 메모리 사용량이 증가한다

- 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization)

- F(n) = F(n-1) + F(n-2)과 같이 점화식 또는 수학적 귀납법으로 적용되는 문제에 적용 할 수 있다.

 

대표적인 문제로는 피보나치 수열이 있다.

 

접근 방법으로는 top->down 형식과 bottom -> up 형식이 있다.

피포나치 수열이란?

1 = 1

2 = 2

3 = 3 = 1 + 2

4 = 3 + 2 = 1 + 2 + 2

와 같이 F(n) = F(n-1) + F(n-2)를 수학적 귀납법으로 만족 하는 수열이다.

 

백준 2748 피보나치수열

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

import sys
sys.stdin = open('inputs.text')

n = int(sys.stdin.readline())

memo = {1:1, 2:1}

def fx(n):
    if n in memo:
        return memo[n]
    memo[n] = fx(n-1) + fx(n-2)
    return memo[n]


print(fx(n))