Data Structure
๐งฉ [Data Structure] ์๋ฃ๊ตฌ์กฐ์ ์ฌ๊ท
โ
1๏ธโฃ ์๋ฃ๊ตฌ์กฐ์ ์ฌ๊ท.
๐ Intro.
- โ๏ธ ์ฌ๊ท: โ๋ด ์์ ๋๋ฅผ ์ฐพ๋ ๊ฒโ
- โ๏ธ ์ฆ, ์ฑ๊ฒฉ์ ๊ฐ๊ณ ํฌ๊ธฐ๋ง ์์ ๋๋ฅผ ์ฐพ์ ํฐ ๋์ ์์ ๋๊ฐ ์ฐ๊ฒฐ๋ ๊ด๊ณ๋ฅผ ๋๋ฌ๋ด๋ ๊ฒ.
โ
2๏ธโฃ ์๋ฃ๊ตฌ์กฐ์ ์ฌ๊ท์ ์์.
- โ๏ธ ํฉํ ๋ฆฌ์ผ(Factorial)
- โ๏ธ 1๋ถํฐ n๊น์ง ๊ณฑํ๋ n!(n ํฉํ ๋ฆฌ์ผ)์ $n!\ =\ 1\ ร\ 2\ ร\ 3 \ ร ๏น๏น๏น\ ร \ (n-1)\ ร\ n$ ์ด๋ค.
- โ๏ธ ์ฌ๊ธฐ์ ๋งจ ๋์ n๋ง ์ ์ธํ๋ฉด $1\ ร\ 2\ ร\ 3 \ ร ๏น๏น๏น\ ร \ (n-1)$์ธ๋ฐ ์ด๊ฒ์ (n-1)!์ด๋ค.
- โ๏ธ n!์ ์ฌ๊ธฐ์ n๋ง ๋ ๊ณฑํ๋ฉด ๋๋ค.
- โ๏ธ โ์ฆ, $n!\ =\ n\ ร\ (n-1)!$โ
- โ๏ธ ํฌ๊ธฐ๊ฐ n์ธ ํฉํ ๋ฆฌ์ผ์ ํฌ๊ธฐ๊ฐ n-1์ธ ํฉํ ๋ฆฌ์ผ์ ํฌํจํ๊ณ ์๋ค.
- โ๏ธ ์ฆ, ์ฑ๊ฒฉ์ ๊ฐ๊ณ ํฌ๊ธฐ๋ง ์์ ๋๋ฅผ ์ฐพ์ ํฐ ๋์ ์์ ๋๊ฐ ์ฐ๊ฒฐ๋ ๊ด๊ณ๋ฅผ ๋๋ฌ๋ธ ๊ฒ์ด๋ค.
- โ๏ธ ์ด์ฒ๋ผ ์ด๋ค ๋ฌธ์ ๋ ํจ์ ๋ฑ์ด ์์ ๊ณผ ์ฑ๊ฒฉ์ด ๋๊ฐ์ง๋ง ํฌ๊ธฐ๊ฐ ๋ ์์ ๋ฌธ์ ๋ฅผ ํ๋ ์ด์ ํฌํจํ๊ณ ์์ ๋ โ์ฌ๊ท์ ๊ตฌ์กฐโ๋ฅผ ๊ฐ๊ณ ์๋ค๊ณ ๋งํ๋ค.
โ
3๏ธโฃ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ ๊ทธ๋ฆฌ๊ณ ์ฌ๊ท์ ๊ด๊ณ.
- โ๏ธ ๋๋ถ๋ถ์ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด๋ ํจ์ ๋ด๋ถ์์ ์์ ์ ํธ์ถํ๋ ์๊ธฐํธ์ถ(์ฌ๊ท) ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ค.
- โ๏ธ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ด๊ณ ์ค์ฌ์ ์ฌ๊ณ ๋ฐฉ์์ ํ๋ จํ๋ ๋๊ตฌ์ด๊ธฐ๋ ํ๋ค.
- โ๏ธ ์ฌ๊ท๋ ํ๋ถ์์ ์๊ณ ๋ฆฌ์ฆ์ ๋ค๋ฃฐ ๋ ๋ช
์์ ์ผ๋ก 40% ์ ๋, ๋ช
์์ ์ผ๋ก ๋๋ฌ๋์ง ์์ง๋ง ์ฌ๊ท์ ์ฑ๊ฒฉ์ ๊ฐ๊ณ ์๋ ๊ฒ ๊น์ง ํฉํ๋ฉด 80% ์ ๋๋ ์ฐจ์งํ๋ ์ฃผ์ ๋ค.
- โ๏ธ ์๋ฃ๊ตฌ์กฐ์์๋ ์๋นํ ๋์ ๋น์จ์ ์ฐจ์งํ๋ค.
- โ๏ธ ์ฌ๊ท๋ฅผ ๋ชจ๋ฅด๊ณ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ ์ ์๋ค.
- โ๏ธ ์ฌ๊ท๋ ์ปดํจํฐ ๊ณผํ ์ด๋ก ์ ๊ทผ๊ฐ์ ์ด๋ฃจ๋ ์ค์ ๊ฐ๋
์ผ๋ก, ์ด๋ ต๊ฑฐ๋ ํน๋ณํ ์ฃผ์ ๊ฐ ์๋๋ค.
- โ๏ธ ์ปดํจํฐ ๊ณผํ์ ๊ณต๋ถํ๋ค ๋ณด๋ฉด ์ฌ๊ท๋ ๋์์์ด ๋ค์ํ ์ผ๊ตด๋ก ์ถํํ๋ค.
- โ๏ธ ๋ฐ๋ผ์ ์ด ์ฃผ์ ์ ๋ํด ์จ ์ฌ๋ฏ์ด ์์ฐ์ค๋ฝ๊ฒ ๋ฐ์๋ค์ฌ์ผ ํ๋ค.