์ฝ๋ฉํ
์คํธ/๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ
2022. 2. 20.
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(Dynamic_Programming)
1. Dynamic_Programming ์ด๋ ํฐ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋ ๋ ์ฃผ๋ก ์ฌ์ฉํ๋ค. ์์ ๋ฌธ์ ์์ ๊ตฌํ ์ ๋ต์ ๊ทธ๊ฒ์ ํฌํจํ๋ ํฐ ๋ฌธ์ ์์๋ ๋์ผํ ๋ ์ฌ์ฉํ ์ ์๋ค. ์ฃผ์์ฌํญ : ์ฌ๊ทํจ์๋ก ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ๊ตฌํ์ ์ฌ๊ทํจ์๋ฅผ ์ ์ฌํ๋ ๋ฉ๋ชจ๋ฆฌ์์ ์ค๋ฒํค๋๊ฐ ๋ฐ์ํ ์์๋ค. ๋ฐ๋ผ์ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์์๋ ์ฌ๊ทํจ์๋ณด๋ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ์ฌ ์ค๋ฒํค๋๋ฅผ ์ค์ผ ์ ์๋ค. ํผ๋ณด๋์น ์์ด์ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ๋ํ ๋ฌธ์ ์ด๋ค. ํ๋ณด๋์น๋ฅผ ํตํด ๋ค์ด๋๋ฏน ํจ์๋ฅผ ์ดํดํด๋ณด์. 2. ์์์ฝ๋(์ฌ๊ทํจ์ ์ฌ์ฉ) d = [0] * 100 # ํ ๋ฒ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ์ด์ ์ด์
(memoization)ํ๊ธฐ ์ํ ๋ฆฌ์คํธ ์ด๊ธฐํ def fibo(x): # ํผ๋ณด๋์น ์์ด์ ์ฌ๊ทํจ์๋ก ๊ตฌํ(ํ ๋ค์ด ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ) if x =..