Dynamic Programming (동적 계획법)
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용(재활용)
일반적인 재귀보다 훨씬 효율적인 계산이 가능하다. 일반적인 재귀는 다음과 같이 동일한 계산들이 반복되는 경우가 많다
그러나 dp를 사용하면 이전에 계산한 값들을 저장해놓기 때문에 다음에 동일한 계산이 오면 또다시 계산하는게 아니라 저장한 결과를 활용한다.
DP의 사용조건
DP가 적용되기 위해선 2가지 조건을 만족해야 한다.
1. 겹치는 부분 문제
2. 최적 부분 구조
겹치는 부분 문제
DP는 기본적으로 문제를 나누고 그 문제의 결과값을 재활용해서 전체 문제를 해결한다. 따라서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
DP는 부분 문제의 결과를 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복해서 나타나지 않는다면 재사용이 불가능하기 때문에 부분 문제가 중복되지 않는 경우에는 사용할 수 없다. 예를 들어 이진 탐색과 피보나치 수열을 비교해보면, 이진 탐색은 위치를 찾으면 바로 반환할 뿐 값을 재사용하지는 않는다. 그러나 피보나치 수열은 동일한 값들이 반복해서 나타나기 때문에 DP를 사용하여 값을 저장&재사용 할 수 있다.
최적 부분 구조
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
만약 A-B까지의 가장 짧은 경로를 찾는 경우가 있다고 하자. 중간에 X가 있을때 A-B로 가는 가장 짧은 경로는 AX2 & BX2 를 거치는 것인데 이는 A-X로 가는 최적의 경로와 X-B로 가는 최적의 경로를 사용한 것과 동일하다.
그리디 알고리즘과 다른 점은, 그리디 알고리즘은 부분 문제의 최적값이 전체 문제의 최적값을 낼 수 없는 경우가 존재하지만, 그리디 알고리즘은 부분 문제의 최적값이 항상 전체 문제의 최적 값을 낼 수 있다는 점이다. 따라서 그리디 알고리즘은 항상 최적해를 보장하지는 않는 반면, 동적 계획법은 항상 최적해를 보장한다. (다만 그리디 알고리즘은 속도가 빠르고, 대부분 최전체 최적값에 대한 좋은 근사치를 가지기 때문에 유용하다.)
DP 사용법
- DP로 풀 수 있는 문제인지 확인(위 2가지 조건을 고려하여)
- 문제의 변수 파악
- 변수 간 관계식 만들기(점화식)
- 변수의 값에 따른 결과를 저장(memoization, tabulation)
- 기저 상태 파악(문제를 해결하기 위해 가장 먼저 필요(사용되는)한 값)
- 구현하기
구현 방법
- Bottom up (Tabulation) - 반복문 사용
- Top-Down (Memoization) - 재귀 사용**
Bottom up
아래에서(기저 상태) 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다. 반복문을 통해 계산을 하고 계산 결과를 누적시키는 과정을 table-filling 이라하고, 줄여서 Tabulation 이라고 한다.
Top down
Bottom up 방식이 반복문으로 기저 상태에서 출발한다면 Top down 방식은 재귀로 최상단에서 출발한다. 위에서부터 호출을 시작하여 기저상태까지 내려간 다음 해당 결과값을 재귀를 통해 전이시켜 재활용하는 방식이다. 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있는 값을 재사용하면 된다. 이러한 방식을 Memoization 이라고 한다.
Bottom up 방식은 밑에서부터 차근차근 값을 계산해나가기 때문에 메모리에 무조건 저장된다. 따라서 값이 존재하는지(계산되었는지) 찾을 필요가 없다. 그러나 Top down 방식은 위에서부터 내려가기 때문에 값이 저장되지 않는 경우가 존재하고, 그럴 경우 계산을 진행하게 된다.
피보나치 수열을 통해 설명을 이해해보자.
Top down 방식의 피보나치 수열
n = int(input())
dp = [0] * (n+1)
def topDown(n):
if n <= 2: return 1
else:
dp[n] = topDown(n-1) + topDown(n-2)
return dp[n]
print(topDown(n))
print(dp) # [0,0,0,...]dp[1],dp[2]를 따로 저장하지 않아도 피보나치 값이 정상적으로 나오긴 하지만 dp배열에는 [0,0,0,2,3,5,...]로 들어가게 된다는 점은 알아두자. 따라서 정확하게 하기 위해 dp[1],dp[2] 값을 설정해주는것도 좋다.
Bottom up 방식의 피보나치 수열
n = int(input())
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n]) # [0,1,1,...]
print(dp)아래서부터 차근차근 쌓아나갔다.
마치며
결과적으로 Bottom Up 방식이나 Top Down 방식 모두 결과값을 저장하고 재사용한다.
