다이나믹 프로그래밍(동적 계획법)
동적 프로그래밍은 하위 문제가 겹치고 최적의 하위 구조 속성이 있는 문제 클래스를 효율적으로 해결하는 데 도움이 되는 컴퓨터 프로그래밍 기술이다.
즉, 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 사용하는 것이다.
DP 는 재귀방식과 아주 유사하다. 큰 차이점은 일반적인 재귀를 사용시 동일한 작은 문제들이 여러번 반복돼 비효율적 계산이 된다.
예시로는 피보나치 수열이다
피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 f(n) = f(n-1) +f(n-2) 식이 나온다
중복돼서 쓰이는 함수가 많은게 보이고 시간복잡도 또한 O(n^2) 이다.
def fibo(x): # 피보나치 함수 생성
if x==1 or x==2: #
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(5)) # O(n^2)DP 적용조건
1)Overlapping Subproblems(겹치는 부분 문제)
Dp 는 문제를 나누고 문제의 결과값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복할 경우 사용 가능하다.
2)Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적결과를 낼 수 있는 겨우를 의미하고 문제의 크기에 상관없이 정답은 동일한다.
구현방식
DP는 두가지 방식으로 구현이 가능하다
1)Bottom-Up 방식 반복문 사용
2)Top-Down 방식(Memoization) 재귀 사용
Bottom-up (Tabluation)
dp = [0]*100 # 방생성
dp[1]=1
dp[2]=1
n=99
# bottom up 방식
for i in range(3, n+1):
dp[i] = dp[i-1]+dp[i-2]
print(dp[n])
Tabluation
반복을 통해 memo[0]부터 하나 하나씩 채우는 과정
table을 채워나간다는 느낌으로, 하나씩 다 미리 계산한다.
Top-Down(Memoization)
memo = [0]*100 # 방 생성
def fibo(x): #topdown 방식
if x==1 or x==2:
return 1
if memo[x] != 0: #이미 방이 차 있으면 그대로 반환
return memo[x]
# 점화식 생성
memo[x] = fibo(x-1)+fibo(x-2) #아직 계산하지 않았다면 결과에 따라 방을 채운다
return memo[x]
print(fibo(99))
-Memoization
이전 계산값을 메모리에 저장하여(메모리 공간을 약간 더 사용한다)(캐싱이라고도 한다.)
매번 다시 실행하지 않도록해서 실행 속도를 빠르게 하는 기술이다.
위에서 부터 호출을 시작하여 memo[0] 의 상태까지 내려간 후 해당 결과 값을 재귀를 통해 재활용 하는 방식이다.
피보나치의 예시처럼 동일한 계산이 반복적으로 나오게 된다.
이미 계산을 완료한 경우에는 메모리에 저장되어 있던 값을 꺼내서 활용하면 된다.
가장 최근상태 값을 메모해뒀다고 하여 Memoization 이라고 한다
Top-Down과 Bottom-Up이 방식과 장단점에서 차이점이 있는데,
Memoization(Top-Down)의 경우 재귀의 호출 스택이 Recursion Error를 발생시킬 수 있다.
Bottom-Up의 경우 어떤 입력이 들어와도 처음부터 계산하기 때문에 불필요한 연산이 생긴다.
재귀는 내부 스택을 만들고 함수를 호출하는 과정이 있어보여 시간적으로 더 효율적이라고 느낄수도 있다. 하지만
Top-Down 을 통해 점화식에 따라 불 필요한 계산을 Bottom-up보다 덜 하는 경우가 있어 제대로 알 수 없다.
엄밀히 말하면 bottom-up 방식은 한번 계산된 결과를 담기만 하고 활용 안하는 경우가 있다
다이나믹 프로그래밍과는 서로 다른 개념일 수 도 있다.
관련문제:https://windy7271.tistory.com/65
출처:
댓글