카테고리 없음
메모이제이션? (memoization)
chaeyoung-
2023. 11. 12. 18:28
메모이제이션 은 값비싼 함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발행할 때 불필요하게 다시 계산하는 대신 캐싱된 결과를 반환하는 프로그래밍 기술입니다.
동일한 입력으로 여러 번 호출되는 함수 또는 컴포넌트가 있을 때 유용합니다.
아래와 같이 활용 할 수 있습니다.
동적 계획법
- 복잡한 문제를 간단한 여러가지 문제로 나눠 푸는 방법
- 중복된 부분을 제외하여 한번만 계산하고도 구할 수 있어 시간,공간 복잡도를 감소시킴
피보나치를 구하는 방법
1) 재귀 함수 호출
숫자가 커질수록 함수를 되풀이하므로 시간이 오래 소요된다. 시간복잡도:O(2^n)
static long fibo(int N) {
if(N<=1)
return N;
else
return fibo(N-1) + fibo(N-2);
}
2) 메모이제이션 활용
한 번 구한 계산을 더이상 계산하지 않고 가져다 쓰는 개념이라 시간이 줄어들 수 있습니다. 시간 복잡도:O(n)
static long[] arr = new long[51]; // 저장 변수 선언
static long fiboMemozation(int N) {
if(N == 0)
return arr[0];
else if(N == 1)
return arr[1];
else if(arr[N] != 0)
return arr[N];
else
return arr[N] = fiboMemoization(N-1) + fiboMemoization(N-2);
}
N의 값이 커지면 커질수록 실행시간도 커집니다.
즉, 동적 계획법을 효율적으로 짜기 위해서는 메모이제이션을 활용할 수 있습니다.
references: