6. ๋ฐฐ์ด (Array)
๋ธ๋ก๊ทธ ๊ธ์ ์ด์ฌํ ์จ๋ณด๋ ค๊ณ ํ์ง๋ง, ์ต๊ทผ์ ์๊ฐ์ ์ ๋ฆฌํ๋ ์๊ฐ์ ๋ง์ด ๊ฐ๊ฒ ๋์์ต๋๋ค.๊ฒฐ๊ตญ ๋ธ๋ก๊ทธ ๊ธ์ ์์ฑํ๋ ๊ฒ์ด ์ณ๋ค๊ณ ์๊ฐํ๊ณ . ๊ธ์ ์ฃผ๋ก ์ฐ๋ ค๊ณ ํฉ๋๋ค.๋ค๋ง, ์ ์๊ฐ์ ์ ๋ฆฌํ๊ณ ๊ธฐ๋ณธ์ ๋ค์ ์ฑ์ฐ๋ ๋๋์ ๋ธ๋ก๊ทธ๋ผ์ ๊ณต๋ถ์ ์ง์นจ์๊ฐ ๋ ์ง๋ ๋ชจ๋ฅด๊ฒ ์ต๋๋ค.๋ช ๋ฒ์ฉ, ๋ฐฉ๋ฌธํ๋ฉด์ ์ ๊ธ์ ์ฝ์ด์ฃผ์๋ ๋ถ๋ค๊ป ๊ฐ์ฌํฉ๋๋ค! ๋ฐฐ์ด์ด๋ ๋ฌด์์ผ๊น?๋ฐฐ์ด์ ์๋ฃ๊ตฌ์กฐ ๊ด์ ์์ ๋ณด๋ฉด ์๋นํ๋ฐ์.ํ์ฌ ๊ธ์ ์นดํ
๊ณ ๋ฆฌ๋ Java์ ๊ธฐ๋ณธ์ด๋ก ์ด๋ฏ๋ก ๋จ์ํ๊ฒ๋ง ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค! ํ์ค๊ณผ ๋น๋์ด ์๊ฐํด๋ณด์. ์ซ์๊ฐ `1, 2, 3, 4`์ ํํ๋ฅผ ๋ ๊ณ ์์ผ๋ฉด ์ฐ๋ฆฌ๋ '์๊ฐ ๋์ด๋์ด ์๋ค.' ๋ผ๊ณ ํ์ฃ ?๊ธ์๊ฐ `ใ
, ใ
ฃ, ใฑ, ใ
, ใ
`์ ํํ๋ฅผ ๋ ๊ณ ์์ ๋, ์ฌ๋ฐ๋ฅธ ๊ธ์๋ก '๋ฐฐ์ด'ํด ๋ณด์ธ์. ๋ผ๊ณ ๋ ํ์ฃ ?์ฌ๋ฐ๋ฅด๊ฒ ๋ฐฐ์ด ํ๋ค๋ฉด..
2024. 2. 10.
[์ด๋ถ ํ์] ์ด๋ถ ํ์(Binary Search) ์ด๋ ?
์ด๋ถ ํ์ ๋ ์ด, ๋๋ ๋ถ์ ์จ์ ์ด๋ถ์ธ๊ฐ? ์ ๋ต, ์ด๋ถ ํ์์ ๋๊ฐ๋ก ๋๋์ด์ ํ์ํ๋ ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด, 1๋ถํฐ 10๊น์ง ์๋ค๊ณ ์๊ฐํด๋ณด์. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ์ฐ๋ฆฌ๊ฐ 8์ ์ฐพ์ ๋, ๋์ผ๋ก ๋ฐ๋ก ๋ณด์ด๋๊น ์์น๋ฅผ ํ์
ํ ์ ์๋ค. ํ์ง๋ง ๋ช ๋ฒ์งธ์ ์๋๊ฐ? ๋ฐฐ์ด์ 0๋ฒ์งธ๋ถํฐ ์์ํ๋ 7๋ฒ์งธ์ ์๋ค๋ ๊ฒ์ ์ ์ ์๋ค. ์ปดํจํฐ ๋ฐฐ์ด ์ธ๋ฑ์ค ๊ฐ๋
์ด ์๋ ์ฌ๋๋ค์ 8๋ฒ์งธ๋ผ๊ณ ๋ตํ ๊ฒ์ด๋ค. ์ฆ, O(1) ์๊ฐ์ด๋ค. ๊ทธ๋ผ, {1, 4, 7, 10, 12, 23, 30, 35, 100, 120} ์ด ์์ ๋, 35์ ์์น๋? ์ฐ๋ฆฌ๋ ์์์ ๊ฐ์ ์ธ์ด๊ฐ๋ฉด์ ๋ช ๋ฒ์งธ์ ์๋์ง ์ ๊ฒ์ด๋ค. ์ฆ, O(N) ์๊ฐ์ด๋ค. 100๋ง๊ฐ์ ์ซ์๊ฐ ์๋ค๋ฉด? ์ฐ๋ฆฌ๋ 100๋ง๊ฐ๋ฅผ ์ผ์ผ์ด ์ธ๋ค๊ฐ..
2024. 2. 1.