은학의 코딩 일기장
[알고리즘]다이나믹 프로그래밍(DP) 본문
다이나믹 프로그래밍이란?
- 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
- 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다.
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
- 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식이 있다.
메모이제이션(Memoization)
- 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다.
- 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
- 메모이제이션은 한 번 구한 정보를 리스트에 저장하는 형태로 구현할 수 있다.
- 이 리스트를 보통 DP테이블이라고 부른다.
동작방식
1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.)
2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션
3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다.
4. 가장 큰 문제를 풀이할때까지 반복한다.
☆무엇을 어떻게 저장할지 정하는게 중요하다.
구현 방법
Bottom-up 방식 (반복문 사용)
아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
Top-down 방식 ( 재귀 사용)
위에서부터 함수를 호출시켜서 재귀로 문제를 해결하는 방식
'알고리즘' 카테고리의 다른 글
[알고리즘] 정렬 (0) | 2023.02.21 |
---|---|
[알고리즘] 완전탐색 (0) | 2023.02.03 |
[알고리즘] BFS (0) | 2023.01.27 |
[알고리즘] DFS (0) | 2023.01.24 |
[알고리즘] 그리디(Greedy) (0) | 2023.01.04 |