DynamicProgramming 1
[Dynamic Programming] ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ๊ธฐ์ดˆ

์ฝ”๋“œ์—†๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ๋‹˜์˜ ๊ฐ•์˜ ์ˆ˜๊ฐ• Dynamic Programming ์กฐ๊ฑด ๋ฌธ์ œ๊ฐ€ ๋” ์ž‘์€ subproblem์œผ๋กœ ์ชผ๊ฐœ์งˆ ๋•Œ subproblem์˜ solution์œผ๋กœ ๋” ํฐ problem์˜ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„ ๋•Œ ๋‚˜๋ˆˆ subprolem์ด ๊ฒน์น  ๋•Œ -> ํ•„์š”ํ•œ ๊ณ„์‚ฐ ์ˆ˜๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค. ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ๋Œ€ํ‘œ์ ์ธ ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ์˜ˆ์‹œ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด F(7)์„ ๊ตฌํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด? F(7) = F(6) + F(5) F(7) = F(5) + F(4) + F(4) + F(3) F(7) = F(4) + F(3) + F(3) + F(2) + F(3) + F(2) + F(2) + F(1) . . . ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š”? ์ธต์ด ๋Š˜์–ด๋‚  ๋•Œ๋งˆ๋‹ค 2๊ฐ€ ๊ณฑํ•ด์ง€๊ณ  ์ด n๊ฐœ์˜ ์ธต์ด๊ธฐ ๋•Œ๋ฌธ์— $$ O(2^n) $$ def fib_naive..
Algorithm/๋™์ ๊ณ„ํš๋ฒ• 2023.10.20
1
๋”๋ณด๊ธฐ

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