๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
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.
728x90
๋ฐ˜์‘ํ˜•

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”