[์ค๋์ ํ ๋ง] Fibonacci Day: ์ฐ์ฃผ๋ฅผ ๊ดํตํ๋ ์๋ฒฝํ ํจํด
Fibonacci Day: ์ฐ์ฃผ๋ฅผ ๊ดํตํ๋ ์๋ฒฝํ ํจํด
11์ 23์ผ์ธ ์ค๋์ ์ ์ธ๊ณ์์ Fibonacci Day๋ก ๊ธฐ๋ ๋๋ค. ๋ ์ง์ธ 1-1-2-3์ด ํผ๋ณด๋์น ์์ด์ ์ฒซ ๋ค ํญ๊ณผ ์ ํํ ์ผ์นํ๊ธฐ ๋๋ฌธ์ด๋ค. ๊ฒ์ผ๋ก ๋ณด๊ธฐ์๋ ๋จ์ํ ์ซ์ ๋์ด์ฒ๋ผ ๋๊ปด์ง์ง๋ง, ์ด ์์ด์ ์์ฐ, ์์ , ๊ฑด์ถ, ๊ณผํ, ๊ธ์ต ๋ฑ ์ธ๋ฅ๊ฐ ๋ง๋ค์ด๋ธ ๊ฑฐ์ ๋ชจ๋ ๊ตฌ์กฐ ์์ ์ค๋ฉฐ ์๋ค.
ํผ๋ณด๋์น ์์ด์ ๋ค์๊ณผ ๊ฐ๋ค: 1, 1, 2, 3, 5, 8, 13, 21… ์์ ๋ ์๋ฅผ ํฉํด ๋ค์ ์๋ฅผ ๋ง๋๋ ๊ท์น์ด๋ค. ๋จ์ํจ์์ ์์ํ์ง๋ง ๊ทธ ์์ ์จ๊ฒจ์ง ์กฐํ์ ๊ท ํ์ ๋๋๋๋ก ๊น๋ค. ์ด ์์ด์ ๊ณ์ ํ์ฅํด ์ฐ์๋ ๋ ์์ ๋น์จ์ ๋น๊ตํ๋ฉด, ๊ถ๊ทน์ ์ผ๋ก ํฉ๊ธ๋น(1.618…)์ ์๋ ดํ๋ค.
✨ ํผ๋ณด๋์น ์์ด์ด ํน๋ณํ ์ด์
์ด ์์ด์ด ์ค์ํ ์ด์ ๋ ‘๋จ์ํจ’์ด ‘์๋ฒฝํจ’์ ๋ง๋ ๋ค๋ ์ฌ์ค์ ์์งํ๊ธฐ ๋๋ฌธ์ด๋ค. ์ค์ธ ์๋์ ์ํ ๋ฌธ์ ์์ ํ์ํ ๊ฐ๋ ์ด์ง๋ง, ์ค์ ์์ฐ๊ณ์์ ๋๋ผ์ด ๋น๋๋ก ๋ฐ๊ฒฌ๋๋ค.
- ๋ฌํฝ์ด ๊ป๋ฐ๊ธฐ์ ๋์
- ํด๋ฐ๋ผ๊ธฐ ์จ์ ๋ฐฐ์ด ํจํด
- ์์ฉ๋์ด ์ํ์ ํ ๊ตฌ์กฐ
- ํ์ธ์ ํ·์ํฐ์ดํฌ์ ๋ฐฐ์ด
- ์ด๋ชฉ์ ๋ฐ์ ํจํด
์ด๋ฌํ ๊ตฌ์กฐ๋ ์๋ช ์ฒด๊ฐ ์๋์ง๋ฅผ ๊ฐ์ฅ ํจ์จ์ ์ผ๋ก ๋ฐฐ๋ถํ๋ ๊ณผ์ ์์ ์์ฐ์ค๋ฝ๊ฒ ๋๋ฌ๋๋ค. ์ฆ, ํผ๋ณด๋์น ์์ด์ ์์ฐ์ ‘์ต์ ํ ์๊ณ ๋ฆฌ์ฆ’์ด์ ‘๋ณดํธ์ ํจํด’์ด๋ผ ํ ์ ์๋ค.
๐ง ๊ธฐ์ ·๊ณผํ ์์ ํผ๋ณด๋์น
ํ๋ ๊ธฐ์ ์์๋ ํผ๋ณด๋์น ๊ตฌ์กฐ๋ ํน๋ณํ ๋น์ค์ ์ฐจ์งํ๋ค. ์ปดํจํฐ ๊ณผํ์์๋ ํจ์จ์ ์ธ ๊ฒ์๊ณผ ๋ฉ๋ชจ๋ฆฌ ๊ตฌ์กฐ์ ํผ๋ณด๋์น ํ(Fibonacci heap) ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ฉฐ, ๊ธ์ต ์์ฅ์์๋ ํผ๋ณด๋์น ๋๋๋ฆผ ๋น์จ์ด ํธ๋ ์ด๋ฉ ๋ถ์์ ํต์ฌ ๋๊ตฌ ์ค ํ๋๋ค. ์ํฅ ๊ณตํ, ์ ํธ์ฒ๋ฆฌ, ์ธ๊ณต์ง๋ฅ ๋ฑ ๋ค์ํ ๋ถ์ผ์์๋ ์ด ํจํด์ ํ์ฉ๋๋ค.
๐ ์ฐ๋ฆฌ๊ฐ ์ค๋์ ๊ธฐ์ตํด์ผ ํ๋ ์ด์
ํผ๋ณด๋์น์ ๋ ์ ๋จ์ํ ‘๊ธฐ๋ ์ผ’์ด ์๋๋ค. ์ฐ๋ฆฌ๊ฐ ์ด์๊ฐ๋ ์ธ๊ณ๊ฐ ํผ๋์ด ์๋๋ผ ‘ํจํด๊ณผ ์ง์’๋ก ์์ง์ธ๋ค๋ ์ฌ์ค์ ์๊ธฐ์ํค๋ ๋ ์ด๋ค. ์ฐ์ฃผ์ ๊ตฌ์กฐ, ์๋ช ์ฒด์ ์ฑ์ฅ, ์ธ๊ฐ์ ์์ ์ ๊ฐ๊ฐ๊น์ง๋ ์ด ์์ด๊ณผ ์ฐ๊ฒฐ๋์ด ์๋ค.
์ค๋ ํ๋ฃจ, ์ฃผ๋ณ ํ๊ฒฝ์ ์กฐ๊ธ ๋ ์ฃผ์ ๊น๊ฒ ๋ฐ๋ผ๋ณด์. ํจํด, ๊ท ํ, ๋ฐ๋ณต ์์์ ํผ๋ณด๋์น์ ํ์ ์ ๋ฐ๊ฒฌํ๊ฒ ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ๊ทธ ์๊ฐ, ์ฐ๋ฆฌ๊ฐ ์ฌ๋ ์ธ๊ณ๊ฐ ์ผ๋ง๋ ์ ๊ตํ๊ฒ ์ค๊ณ๋์ด ์๋์ง ์์ผ ๋๋ผ๊ฒ ๋๋ค.