DP, Dynaminc Programming

DP, Dynaminc Programming

동적 계획법

---

피보나치 수열

Fibonacci numbers

모든 항은 바로 앞 두 항의 합인 수열

1, 1, 2, 3, 5, 8, ...

 

📄 피보나치 수열-재귀함수

input = 20

def fibo_recursion(n):
    if(n<3):
        return 1
    else:
        return fibo_recursion(n-2) + fibo_recursion(n-1)



print(fibo_recursion(input))  # 6765

하지만, n에 100을 넣으면 값이 나오는데 엄청난 시간이 걸림.

이유? 연산량이 많기 때문

 

그렇기 때문에 여태까지 했던 연산 결과를 기록해 다시 활용할 수 있는 DP 개념이 생김!!!

---

동적 계획법(Dynamic Programming)이란?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

부분 문제 반복과 최적 부분 구조를 가지고 일반적인 방법에 비해

더욱 적은 시간 내에 문제를 풀 수 있는 방법

 

📌 Memoization

결과를 기록하는 것

 

📌 Overlapping Subproblem

문제를 쪼갤 수 있는 구조, 겹치는 부분 문제

 

📌 피보나치 수열-DP 구현 방법

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

memo = {
	1: 1, # Fibo(1)의 값을 기록
    	2: 1, # Fibo(2)의 값을 기록
}

 

📄 피보나치 수열-DP

Top Down 방식 이용.

Fifo(100) → Fifo(99) → Fifo(98) → ...

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}

# 1. 만약 메모에 있으면 그 값을 바로 반환하고
# 2. 없으면 아까 수식대로 구한다
# 3. 그리고 그 값을 다시 메모에 기록한다.

def fibo_dynamic_programming(n, fibo_memo):
    if(n in fibo_memo.keys()):
        return memo[n]
    else:
        fibo_memo[n] = fibo_dynamic_programming(n-1, fibo_memo) + fibo_dynamic_programming(n-2, fibo_memo)
        return fibo_memo[n]

print(fibo_dynamic_programming(input, memo))