-
[자료구조] 메모이제이션(Memoization)Algorithm/자료구조 2024. 5. 9. 19:38
메모이제이션(Menoization)
동일한 문제를 반복해야하는 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식이다.
메모이제이션을 이용하면 중복 계산을 줄일 수 있다.
메모이제이션 방법으로는 TOP-DOWN 방식과 BOTTOM-UP 방식이 있다.
TOP-DOWN
문제 해결이 위에서부터 아래로 진행되는 방식이다.
int arr[] = new arr[t]; int fibonaci(int n){ if(n<=2) { return 1; } if(arr[n] == null){ arr[n] = fibonaci(n-1) + fibonaci(n-2); } return arr[n]; }
fibonaci(10)을 호출하면 fibonaci(10)부터 작은 수를 호출하며 가장 작은 수까지 도달하게 된다.
BOTTOM-UP
문제 해결이 아래에서부터 위로 진행되는 방식이다.
int fibonaci(int n){ arr[0] = 0; arr[1] = 1; for(int i=2; i<=n; i++){ arr[i] = arr[i-1] + arr[i-2]; } return arr[n]; }
fibonaci(10)을 호출하면 arr[2]부터 arr[10]까지 점진적으로 위로 도달하게 된다.
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] 완전 탐색 : 브루트 포스 알고리즘 (0) 2024.05.14 [자료구조] 분할 정복(divide and conquer)알고리즘 (0) 2024.05.10 [자료구조] 동적계획법(dynamic programming, DP) (0) 2024.05.09