728x90 ๋ฐ์ํ ๋์ ํ๋ก๊ทธ๋๋ฐ1 [DP ๊ฐ๋ ] Dynamic Programming#1_ํผ๋ณด๋์น ์์ด,Memoization,Bottom-up ๋ฐฉ์ ํผ๋ณด๋์น ์์ด f(n) = f(n-1) + f(n-2) (๋จ, n>2) ์ด๊ฒ์ ์๋ฐ ์ฝ๋๋ก ๊ตฌํํด ๋ณด๋ฉด, fib(3)์ด๋ฉด ๊ฒฐ๊ณผ๋ 2์ผ ๊ฒ์ด๋ค. f(1)=1์ด๊ณ ,f(2)=1์ด๊ธฐ ๋๋ฌธ์ f(3)์ 2๊ฐ ๋๋ค. Memoization ํผ๋ณด๋์น ์์ด์ ์ด๋ฏธ ๊ณ์ฐํ ์๋ฅผ ์ค๋ณต์ผ๋ก ๊ณ์ฐํ๋ ๊ฒฝ์ฐ๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ๊ต์ฅํ ๋นํจ์จ์ ์ด๋ค. ๊ณ์ฐ์ ์ค๋ณต์ ํผํ๊ธฐ ์ํด ์ด๋ฏธ ๊ณ์ฐ๋ ๊ฐ์ ๊ธฐ์ตํด๋๋ ๊ฒ. Memoization์์ ์ ์ฅํด ๋์ ๋ฐฐ์ด์ cache ๋ผ๊ณ ๋ถ๋ฅธ๋ค. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class DP { static int[] f = new int[10000]; static int fib(int n) { if (n == 1 || n == 2) { ret.. 2021. 7. 26. ์ด์ 1 ๋ค์ 728x90 ๋ฐ์ํ
