.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
동적 계획법
•
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
◦
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
•
다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑 다운과 바텀 업)으로 구성됨
•
시간 복잡도
◦
메모이제이션을 이용하는 경우: O(N)
•
큰 문제들을 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 방식 = 기억하며 풀기.
사용 이유
•
일반적인 재귀방식은 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다.
→ 동일한 계산은 메모이제이션으로 저장하여 문제를 효율적으로 개선할 수 있다.
다이나믹 프로그래밍(DP)의 조건
1.
최적 부분 구조(Optimal Substructure)
•
동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능
•
부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 함
→ 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
2.
중복되는 부분 문제(Overlapping Subproblem)(여러 번 등장)
•
동일한 작은 문제를 반복적으로 해결해야 한다.
•
부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
•
특정 문제의 정답은 문제의 크기에 상관없이 항상 동일
•
부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
DP 사용하기
1.
문제 조건 확인하기
•
특정 데이터 내 최대화 / 최소화 계산
•
특정 조건 내 데이터를 세야 한다거나 확률 등의 계산
2.
문제 변수 파악
•
문제 내 변수의 개수 파악
◦
ex) 피보나치 수열 : n번째 숫자를 구하므로 n이 변수
◦
문자열 간의 차이 : 문자열 길이, Edit 거리 등 2가지 변수
◦
Knapsack 문제 : index, 무게 2가지 변수
3.
변수 간 관계식 만들기
•
점화식 : 인접한 항들 사이의 관계식
◦
결과값이 달라지지만 동일한 변수값인 경우 결과는 동일
◦
그 결과값을 그대로 이용할 것이므로 관계식을 만들어내야 함
•
ex) 피보나치 수열 : an = an-1 + an-2 |||| a1 = 1, a2 = 1
4.
메모하기
•
변수의 값에 따른 결과 저장을 진행해야 함
⇒ 메모이제이션(Memoization)
•
변수 값에 따른 결과를 저장할 배열 등을 미리 만들어 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
•
보통 배열을 쓰며 변수 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
5.
기저 상태 파악
•
가장 작은 문제의 상태
•
예시를 손으로 테스트해서 구성하는 경우가 다수
◦
피보나치 수열 : f(0) = 0, f(1) = 1
•
기저 문제에 대해 파악 후 미리 배열 등에 저장
6.
구현
•
Bottom-Up (Tabulation 방식) - 반복문 사용
•
Top-Down (Memoization 방식) - 재귀 사용
구현 방법
Bottom-Up (Tabulation 방식) - 반복문 사용
•
아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
•
p[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식
•
Tabulation
◦
table-filling : 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정
Top-Down (Memoization 방식) - 재귀 사용 = 캐싱
•
위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
•
동일한 계산이 나올 경우 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용
•
Memoization
◦
가장 최근의 상태 값을 메모
예시 : 피보나치
•
단순 재귀
# 피보나치 - 단순 재귀
def fibo(x):
if x == 1 or x == 2 :
return 1
return fibo(x - 1) + fibo(x - 2)
fibo(10)
Python
복사
•
탑다운 다이나믹 프로그래밍(재귀)
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화 0 ~ 99
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환(메모이제이션)
if d[x] != 0:
return d[x]
# 계산하지 않은 문제는 점화식에 따라 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))
Python
복사
•
피보나치 - 바텀업 다이나믹 프로그래밍(반복문)
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화 0 ~ 99
d = [0] * 100
# 첫 번째 피보나치 수와 두 번쨰 피보나치 수는 1
d[1], d[2] = 1, 1
n = 99
# 피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
Python
복사
그렇다면 무슨 방식이 더 나은가?
•
효율성은 둘 다 뭐가 더 나은 지 알 수 없다.
•
Python의 경우는 Top-Down 방식에서 StackOverflow가 나오는 경우가 많아 Bottom-up 방식으로 사용
•
피보나치 1000을 넣었을 때 결과
1.
Top-Bottom : 0.0010237693786621094
2.
Bottom-Up : 0.0
분할 정복과 동적 프로그래밍
•
공통점 : 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점
•
차이점
◦
분할 정복 : 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 사용
◦
동적 프로그래밍 : 분할된 하위 문제가 동일하게 중복이 일어나는 경우에 사용
