๐ Memoization - ๋ฉ๋ชจ์ด์ ์ด์
๐ซ Memoization
๋ถํ ์ ๋ณต์ ์ฅ์ (์ง๊ด์ ์ด๊ณ ๊ฐ๊ฒฐ)๊ณผ ๋์ ๊ณํ๋ฒ์ ์ฅ์ (๋ถ๋ฌธ์ ํด๋ต์ ์ฌ์ฌ์ฉ)์ ๊ฒฐํฉ
๋ถ๋ถ์ ์ธ ๊ฒฐ๊ณผ๋ค์ ๊ธฐ๋กํ ํ ๋์ค์ ํ์ํ ๋ ๋ค์ ๊ณ์ฐํ ํ์ ์์ด ์ฌ์ฌ์ฉํ๋ ๊ธฐ๋ฒ
@ 4_0001
๋ถํ ์ ๋ณต์ ์ฅ์ /์ธ๊ด (์ง๊ด์ ์ด๊ณ ๊ฐ๊ฒฐ)
๋์ ๊ณํ๋ฒ์ ์ฅ์ /๋ด๋ถ (์ฑ๋ฅ - ๋ถ๋ฌธ์ ํด๋ต์ ์ฌ์ฌ์ฉ)
๊ฒฐํฉ
๋ถํ ์ ๋ณต์ ๊ฐ์ ์ด๋, DP์ ํํฅ์ ์ ๊ทผ์ด๋
(์ด๋์ชฝ์ ๊ฐ์ ์์ผฐ๋๊ฐ์ ๋ํ ์๊ฒฌ์ด ์์ง๋ง ์ผ๋จ์)
๋ฉ๋ชจ๋ฆฌ๋ฅผ ํฌ์์์ผ ์คํ ์๊ฐ์ ์ด์ ์ ์ป์
1
2
3
4
5
6
7
8
9
10
int[] M = new int[MAX_SIZE]{0, 1};
int MemoFib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (M[n] == 0)
M[n] = memo_fib(n - 1) + memo_fib(n - 2);
return M[n];
}
์ด ๊ธฐ์ฌ๋ ์ ์๊ถ์์ CC BY 4.0 ๋ผ์ด์ผ์ค๋ฅผ ๋ฐ๋ฆ
๋๋ค.