๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ1

[DP๊ธฐ์ดˆ] ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ ์ฝ”๋“œ์—†๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋‹˜์˜ DP๊ฐ•์˜ ์ค‘ ์ตœ์†Œ๋น„์šฉ ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ ๊ฐ•์˜๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค https://www.youtube.com/watch?v=lhZTYwHgrDM&list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v&index=3 ๊ณ„๋‹จ์ด n๊ฐœ๊นŒ์ง€ ์žˆ์„ ๋•Œ, n์ธต์— ์˜ฌ๋ผ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ f(n)=f(n-1)+f(n-2)์ด๋‹ค. f(1)=1 f(2)=2 --> ํ•œ์นธ ์”ฉ, ํ•œ๋ฒˆ์— ์˜ฌ๋ผ๊ฐ€๋Š” f(3)=3 ๋“ฑ๋“ฑ์ด๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๊ฐ€์žฅ ์ตœ์†Œ๋น„์šฉ์œผ๋กœ ๊ณ„๋‹จ์„ ์˜ฌ๋ผ๊ฐ€๋Š” ๋ฐฉ๋ฒ•์„ ์•Œ์•„๋ณด์ž. [1,2,4,6,2] ์˜ 5์ธต์˜ ๊ณ„๋‹จ์ด ์žˆ๋‹ค. f(0)=0+1์ด๋‹ค ์™œ๋ƒํ•˜๋ฉด ๋ฐ”๋‹ฅ์—์„œ ํ•œ๋ฒˆ์— ์˜ฌ๋ผ๊ฐˆ ์ˆ˜ ์žˆ๊ณ , arr[0]=1(์—ฌ๊ธฐ์„œ arr[0]์€ 0์ธต์˜ ๊ฐ’์„ ๋‚˜ํƒ€๋ƒ„) ์ด๋ฏ€๋กœ 0+1=1์ด๋‹ค. f(1)=0์ด๋‹ค. ์–˜๋„ ๋ฐ”๋‹ฅ์—์„œ .. 2021. 8. 6.
728x90
๋ฐ˜์‘ํ˜•

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