동적 계획법 개요
동적 계획법(Dynamic Programming)이 뭔데?
특징
- 큰 문제를 작게
- 피보나치를 점화식으로 간단하게 표현하고, f(4)를 구하는 걸 f(3)과 f(2)와 f(1)을 구하는 문제로 쪼개는 그런 걸 얘기하는 듯
- 같은 문제는 한번씩만
두가지 방식:
- 탑다운(Top-Down): Backward Chaining의 일종 / Memoization 기법 / Recursive Function 사용
- 보텀업(Bottom-Up): Forward Chaning의 일종 / Loop 사용
(오버헤드 측면에서 Top-Down보다 성능이 좋다.
동적 계획법은 기본적으로 이 Bottom-Up을 말함)
Memoization이란?
: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
→ 동적계획법을 구현하는 하나의 기법(특히 Top-Down)
피보나치 수열 구현
- 동적 계획법 없이는 반복호출로 인해 시간이 오래걸리는 문제
- 동적 계획법이 왜 필요한데? 에 대한 예시
시간 오래 걸리게 풀기
수열 = 리스트, 점화식 = 재귀함수
로 둔다면, 피보나치 수열은 다음과 같이 구현될 수 있을거다
def fibo(x):
if x == 1 or x==2:
return 1
return f(x-1) + f(x-2)
fibo(6)# seudo code
1. 만약 인풋이 1이거나 2이면 1을 반환해
2. 아니라면, 그 전 + 그 전전을 반환해 그러나 이 경우, 같은 연산이 쓸데없이 많이 중복되는 문제가 생긴다. 예를 들어 f(6)을 구하기 위해 f(3)라는 동일한 함수가 3번이나 반복되어 호출된다. 숫자가 커질수록 당연히 시간 복잡도는 기하급수적으로 늘어나게 될 것: O(2_N)
아래처럼 동적 계획법(이하 DP)을 통해 이 문제를 극복할 수 있음
Top-Down방식의 DP 사용해 시간 절약하기
d = [0]*100
def fibo(x):
if x ==1 or x==2:
return 1
elif d[x] != 0:
return d[x]
else:
d[x] = d[x-1] + d[x-2]
return(d[x])
fibo(6)# seudo code
1. 메모용 리스트를 만든다. 초기값 대충 설정해주고,
2. 함수를 구현해. 일단 첫항/두번째항인지부터 확인. 맞으면 1
3. 그 다음 계산한 적 있는 문제인지 판단. 메모용 리스트 값이 초기값과 같은지 확인.
다르면 그냥 그 값을 반환해. 새로 계산 X
4. 아직 계산 안한거면 점화식 구현+계산 -> 그 값을 메모용 리스트에 저장 Bottom-Up 방식의 DP 사용해 시간 절약하기
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])# seudo code
첫번째, 두번째 수열항 값은 미리 직접 지정
반복문으로 3번째 ~ n번째 값을 '순차적으로' 계산How to Notice
동적 계획법 쓰는 문제인지 어케 알아
-
완전 탐색을 했을 때, 시간이 너무 오래걸린다면 의심하자
- 의심된다면) 해결해야하는 문제들이 중복되는지 check
-
just write down inefficient recursive func
-
if sth seems repetitive,
- fix code w/ memozation
- if it works, would be good to transfer to bottom-up, too
- fix code w/ memozation
.