Algorithm ๋ฌธ์ ๋ฅผ ํ๋ ๋ณดํต while์ด๋ for๋ฌธ ๊ฐ์ ๋ฐ๋ณต๋ฌธ์ ์ด์ฉํด ๋ฌธ์ ๋ฅผ ํ๊ณค ํ๋ค.ํ์ง๋ง ๋ฐ๋ณต๋ฌธ ๋ง์ผ๋ก๋ ํ๊ธฐ ์ด๋ ค์ด ๋ฌธ์ ๋ค์ด๋, ์ฌ๊ท ํจ์๋ก ํธ๋ ๊ฒ์ด ๋ ๋น ๋ฅด๊ฒ ์ ๊ทผ ๊ฐ๋ฅํ ๋ฌธ์ ๋ค์ ๊ฒฝ์ฐ(DFS, DP, Combination ๋ฑ) ์ฌ๊ท ํจ์๋ฅผ ์ฌ์ฉํ
Bubble Sort๋ Selection Sort์ ์ ์ฌํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๋ก ์ธ์ ํ ๋ ์์์ ๋์๋ฅผ ๋น๊ตํ๊ณ , ์กฐ๊ฑด์ ๋ง์ง ์๋ค๋ฉด ์๋ฆฌ๋ฅผ ๊ตํํ๋ฉฐ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.์๊ฐ๋ณต์ก๋๋ฅผ ๊ณ์ฐํ๋ฉด, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(
BFS(Breadth First Search, ๋๋น ์ฐ์ ํ์)๋ ๋ฃจํธ ๋ ธ๋(ํน์ ์์ ๋ ธ๋)์์ ์์ํด์ ์ธ์ ํ ๋ ธ๋๋ค ๋ถํฐ ํ์ํ๋ ๋ฐฉ๋ฒ์ด๋ค. ์์ ๋ ธ๋๋ก๋ถํฐ ๊ฐ๊น์ด ๋ ธ๋๋ฅผ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ ๋ฉ๋ฆฌ ๋จ์ด์ ธ ์๋ ๋ ธ๋๋ฅผ ๋์ค์ ๋ฐฉ๋ฌธํ๋ ํ์ ๋ฐฉ๋ฒ์ด๋ค.
DFS๋ ๋ฃจํธ ๋ ธ๋๋ ์์์ ๋ ธ๋์์ ์์ํ์ฌ ์ต๋ํ ๊น์ํ ๋ค์ด๊ฐ์ ํ์ํ ํ ๋ค์ ์์ ์ผ๋ก ๋์๊ฐ ๋ค๋ฅธ ๋ฃจํธ๋ก ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ฆ, ๋ค์ ๋ ธ๋๋ก ๋์ด๊ฐ๊ธฐ ์ ํด๋น ๋ ธ๋์ ๋ถ๊ธฐ์ ๋ํด ์์ ํ์์ ํ๋ ๋ฐฉ์์ด๋ค. ๋์ด์ ๊ฐ ๊ธธ์ด ์์๋๊น์ง ๊น์ด ์ฐพ์๊ฐ๋ฉด์ ํ์
๋ณธ ๊ฒ์๊ธ์ ์์ฑ์ ๋ณธ์ธ์ ํ์ต์ ์ํจ์ด๋ผ ๋ถ์กฑํ ์ ์ด ๋ง์ต๋๋ค.์ ์๋๋ค์ ๋ฐ๋ปํ ์กฐ์ธ๊ณผ ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค! ๊ฐ์ฌํฉ๋๋ค! ๐โโ๏ธ์ ํ ์ ๋ ฌ(Selection Sort)์ ์ ์๋ฆฌ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ํ๋๋ก ๋น๊ตํ๋ ๊ฒ์ด ์์ ์๊ฐ์ ์ด๋ฃจ์ด์ง๋ค๋ ๊ฐ์ ์๋, n๊ฐ์ ์ฃผ์ด์ง
๋ณธ ๊ฒ์๊ธ์ ์ต ์ฐ์ ๋ชฉ์ ์ ์์ฑ์ ๋ณธ์ธ์ ํ์ต์ ์ํจ์ด๋ผ ๋ถ์กฑํ ์ , ํ๋ฆฐ ๋ถ๋ถ ๋ฑ์ด ๋ง์ต๋๋ค. ์ ์๋๋ค์ ๋ฐ๋ปํ ์กฐ์ธ๊ณผ ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค! ๊ฐ์ฌํฉ๋๋ค! ๐โโ๏ธํ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์๋ ์ง๋๋ฒ ๋์ ๊ณํ๋ฒ(Dynamic Programming)์ ๋ํด์ ์ ๋ฆฌํ๋ฉด์
๋ณธ ๊ฒ์๊ธ์ ์ต ์ฐ์ ๋ชฉ์ ์ ์์ฑ์ ๋ณธ์ธ์ ํ์ต์ ์ํจ์ด๋ผ ๋ถ์กฑํ ์ , ํ๋ฆฐ ๋ถ๋ถ ๋ฑ์ด ๋ง์ต๋๋ค. ์ ์๋๋ค์ ๋ฐ๋ปํ ์กฐ์ธ๊ณผ ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค! ๊ฐ์ฌํฉ๋๋ค! ๐โโ๏ธ์ฝ๋ฉ ํ ์คํธ ๋ฌธ์ ๋ฅผ ํ๋ค๋ณด๋ฉด ์๋์ ๊ฐ์ ์ ํ์ฌํญ์ด ์ข ์ข ๋์ค๊ณค ํ๋ค.๊ฐํน ์ ํ์ฌํญ์ ์ฃผ์ด์ง๋ ์ซ์์