[메모이제이션과 동적계획법]
메모이제이션은 미리 계산한 캐시값을 이용한 최적화 기법이다.
동적 계획법은 하위 문제에서 계산한 값을 재귀 내지는 반복적으로 문제 풀이에 사용하는 기법이다.
주로 table작성(tabulation기법)을 활용 하지만 메모이제이션 방법을 사용 하기도 한다.
메모이제이션과 동적계획법은 어느 한쪽이 서로에게 속하는 관계가 아니다.
[메모이제이션과 tabulation]
tabuation은 bottom-up방식으로 상위 문제를 풀기위해 하위문제의 모든 값을 필요로 할떄 유용하다.
memoization은 top-down방식으로 이미 푼 문제의 값을 저장하고 있는 것이다. top down의 의미는 top단의
문제부터 푼다는 의미이다.
f(7)값을 구한다 치면,
tabulation은 f(1)~f(7)값을 서서히 구해가는 것이고
memoizaiton 은 f(6)을 구할떄 f(2) f(3)이 필요하다 치면 f(2),f(3),f(6)값을 저장 해놓는 것이다. f(7)을 구할때 f(3),f(6),f(4)가 필요하다고 치면 f(3), f(6)값은 가져다 쓰고 f(4)는 다시 구해서 저장 해 놓아야 한다.
(아래내용해석하구 설명덧댄겁니다.)
What is the difference between memoization and dynamic programming?
What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?
stackoverflow.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> rod_value;
map<int, int> rod_max;
int main(void)
{
rod_max[0] = rod_value[0];
for (int i = 0; i < 11; i++)
{
int rod_max_temp = 0;
for (int j = 1 ; j <= i; j++)// j = 1 이어야 한다, 그렇지 않으면 max[5]값을 모른는데 max[5]값을 사용하게 된다.
{
rod_max_temp = max(rod_max[i - j] + rod_value[j], rod_max_temp);
}
rod_max[i] = rod_max_temp;
}
for (map<int, int>::iterator iter = rod_max.begin(); iter != rod_max.end(); ++iter)
{
cout << (*iter).first << "," << (*iter).second << endl;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
|
knapSack문제 풀기전에 좀더 쉬운 연습문제.
동적계획법에서 동적은 큰 의미 없는 이름이다.
map을 별로 써본적이 없어서 연습겸 써봤다.
'프로그래밍 > [Algorithm]' 카테고리의 다른 글
| [Algorithm] DP-2 동적 테이블을 작성하는 Knapsack 예제풀이이다. (0) | 2020.06.01 |
|---|---|
| [Algorithm] 다익스트라 알고리즘 (0) | 2020.05.07 |
| [Algorithm]그래프 입력받기 (0) | 2020.05.06 |
| [Algorithm] dfs 간단 구현 (단지 번호 문제) (0) | 2020.04.27 |
| [Algorithm]merge sort 병합정렬 (0) | 2020.04.22 |
