< Dynamic Programming(동적 계획법) >
- 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다.
- 부분 문제 반복(Overlapping subproblems)과 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
➰ 분할정복(Divide and Conquer)과 비슷하지 않나?
- 비슷하지만 결정적인 차이점이 있다.
- 작은 문제가 중복이 일어나는지 안일어나는지가 분할정복과 동적 계획법의 차이다.
- 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어 푸는 방법 -> 작은 문제에서 반복이 일어나지 않는다
- 동적계획법은 작은 부분 문제들이 반복된다!!!!
➰ Dynamic Programming 조건
- 작은 문제가 반복해서 일어나는 경우
- 같은 문제는 구할 때마다 정답이 같다
➰ Dynamic Programming 방법
- 모든 작은 문제들은 한번만 풀어야 하기 때문에 정답을 구한 작은 문제들은 어딘가에 메모해야 한다
- 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 메모한 작은 문제의 결과값을 이용한다
🌼 좋은 예시 - 피보나치 수열
이런 피보나치 수열을 트리 형태로 나타내면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 알 수 있다.
이때 문제점이 있는데, 소문제의 결과가 상위문제의 결과를 찾는 데 사용됨으로 각각의 소문제는 중복될 수가 있다. 이렇게 되면 같은 소문제를 여러번 반복해서 계산하다 보니 자원낭비가 심해진다.
이럴때 동적 계획법은 소문제의 답을 따로 메모해두고 이를 더 큰 문제를 푸는데 이용한다.
그래서 자원 절약과 시간 절약을 한다!!
✔ Memoization (Top-Down, 하향식)
- 하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어나가는 방법
dp = [0]*100 # 소문제 결과를 저장할 리스트
dp[0] = 1
dp[1] = 1
def fib(n):
# 만약 계산한 적이 없다면 재귀로 계산
if dp[n] == 0:
dp[n] = fib(n-1) + fib(n-2)
# 있다면 그대로 반환
return dp[n]
fib(10)
✔ 상향식, Bottom-Up
- 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용해서 큰 문제의 정답을 풀어나가는 방법
def fib(n):
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
# 작은 값(소문제)부터 직접 계산하며 진행
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
[알고리즘] 다이나믹 프로그래밍 with Python
💡 다이나믹 프로그래밍 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법이다. 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 '분할 정복' 알고리
doing7.tistory.com
동적계획법(Dynamic Programming) 정리글_Python
동적계획법에 대한 정리글입니다. (피보나치 수열 파이썬 구현)
velog.io
[알고리즘] Dynamic programming (동적 계획법) 완전정복 with Python
동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래
lsh424.tistory.com
'알고리즘 > 알고리즘&자료구조' 카테고리의 다른 글
| [알고리즘] 정렬 알고리즘 ( 버블, 선택, 삽입, 퀵, 계수 ) (0) | 2022.04.15 |
|---|---|
| [알고리즘] DFS(깊이 우선 탐색) / BFS(너비 우선 탐색) (0) | 2022.04.08 |
| [알고리즘] 이진 탐색 / 이분 탐색 (Binary Search) (2) | 2022.03.30 |
| [알고리즘] 탐욕 알고리즘(Greedy Algorithm) (0) | 2022.03.18 |
