
๊ธฐ์ ๋ฉด์ ์ค๋นํ๊ธฐ - ์๋ฃ๊ตฌ์กฐ
ยท
๐CS-๋ฉด์
๋ฐฐ์ด(Array)๋ฐฐ์ด์ ์ฅ๋จ์ ์? ์ฅ์ ์ธ๋ฑ์ค๋ฅผ ์ด์ฉํ ๋น ๋ฅธ ์ ๊ทผ(O(1)) ์ฐ์๋ ๊ณต๊ฐ์ ์ฌ์ฉํด์ ๋ฉ๋ชจ๋ฆฌ ํจ์จ์ฑ์ด ์ข๋ค. ๋จ์ ๋ฐ์ดํฐ๊ฐ ์์ฐจ์ ์ผ๋ก ์กด์ฌํด์ ์ค๊ฐ์ ์์๊ฐ ์ฝ์
๋๊ฑฐ๋ ์ญ์ ๋๋ ๊ฒฝ์ฐ ๋ค์ ์๋ ๋ชจ๋ ์์๋ค์ ํ์นธ์ฉ ์์ง์ฌ์ค์ผ ํ๋ค. O(n) ๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ฐจ์ด์ ๋ฐฐ์ด์ ๊ณ ์ ๋ ํฌ๊ธฐ์ ์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๋ธ๋ก์ ์ฌ์ฉํ์ง๋ง, ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋์ ์ผ๋ก ํฌ๊ธฐ๊ฐ ๋ณํ ์ ์๋ ๋
ธ๋๋ค์ ์ฐ๊ฒฐ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ฅผ ํตํด O(1) ์ ์๊ฐ ๋ณต์ก๋๋ก ์์์ ์ ๊ทผํ ์ ์์ง๋ง, ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ํน์ ์์์ ์ ๊ทผํ๊ธฐ ์ํด O(n)์ ์๊ฐ ๋ณต์ก๋๊ฐ ํ์ํ๋ค. ์ฝ์
๊ณผ ์ญ์ ์ ๋ฐฐ์ด์ ๊ฐ ์์๋ค์ ์ฎ๊ฒจ์ฃผ์ด์ผ ํดO(n)์ ์๊ฐ ๋ณต์ก๋๊ฐ ํ์ํ์ง๋ง, ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ O(1)์ ์๊ฐ ๋ณต์ก๋๊ฐ ํ์ํ๋ค. ์ฐ๊ฒฐ๋ฆฌ์คํธ(L..