1. ์ ๋ ฌ๋ ๋ฐฐ์ด
- orderred array: ๊ฐ์ด ํญ์ ์์๋๋ก ์กด์ฌํ๋ ๋ฐฐ์ด
- ์ฝ์ ํ ๋๋ ํญ์ ์ฝ์ ์ ์ ๊ฐ์ ์ฌ๋ฐ๋ฅธ ์์น๋ฅผ ์ฐพ๊ณ , ๋ค๋ฅธ ๊ฐ๋ค์ ์ฎ๊ฒจ ๊ณต๊ฐ์ ๋ง๋ค์ด์ผ ํ๋ค.
- O(N)
- ์ฝ์
์ ํ์ํ ๋จ๊ณ ์๋ ์ ๊ฐ์ด ์ ๋ ฌ๋ ๋ฐฐ์ด ์ด๋์ ๋์ด๊ฒ ๋๋ ๋น์ทํ๋ค
- ์ ๋ถ๋ถ์ ์ฝ์ ํ ๊ฒฝ์ฐ, ๋น๊ต๊ฐ ์ค์ด๋ค๊ณ ์ด๋์ด ๋์ด๋จ
- ๋ท ๋ถ๋ถ์ ์ฝ์ ํ ๊ฒฝ์ฐ, ๋น๊ต๊ฐ ๋์ด๋๊ณ ์ด๋์ด ์ค์ด๋ฌ
2. ์ ๋ ฌ๋ ๋ฐฐ์ด์ ๊ฒ์
- ์ ํ ๊ฒ์: ์์์๋ถํฐ ๊ฒ์
- ์ด ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๋ O(N)์ด๋ค.
- ๊ทธ๋ฌ๋ ๋ ๋์ ๋ฐฉ๋ฒ์ด ์๋ค…
3. ์ด์ง ๊ฒ์(์ด์ง ํ์, Binary Search)
- 1์์ 100 ์ฌ์ด์ ์
๋ค์ด ๊ฒ์์ ์๊ฐํด ๋ณด์.
- 50, 25, 13… ์ฐพ๋ ๊ฐ์ ๋ฒ์๋ ์ ๋ฐ์ ์ ๋ฐ์ ์ ๋ฐ์ผ๋ก ์ค์ด๋ ๋ค.
4. ์ด์ง ๊ฒ์ ๋ ์ ํ ๊ฒ์
- ์์ ํฌ๊ธฐ์ ์ ๋ ฌ๋ ๋ฐฐ์ด์ด๋ผ๋ฉด ์ด์ง ๊ฒ์์ด ์ ํ ๊ฒ์๋ณด๋ค ํฌ๊ฒ ๋์ ์ ์ด ์๋ค.
- ๊ทธ๋ฌ๋ ๋ฐฐ์ด์ด ๋ ์ปค์ง๋ฉด?
- 100๊ฐ์ ๊ฐ์ ๊ฐ์ง ๋ฐฐ์ด์์ ๊ฒ์์ ํ์ํ ์ต๋ ๋จ๊ณ ์
- ์ ํ ๊ฒ์: 100
- ์ด์ง ๊ฒ์: 7 (100์ log 2๋ฅผ ์ทจํ ๊ฐ)
- ์ฆ, ๋ฐ์ดํฐ์ ์์ด 2๋ฐฐ๋ก ๋์ด๋ ๋๋ง๋ค ์ด์ง ๊ฒ์์ ์ต๋ ํ ๋จ๊ณ๋ง ๋ ์ถ๊ฐ๋๋ค.
- 200๊ฐ์ ๊ฐ์ ๊ฐ์ง ๋ฐฐ์ด์์ ๊ฒ์์ ํ์ํ ์ต๋ ๋จ๊ณ ์
- ์ ํ ๊ฒ์: 200
- ์ด์ง ๊ฒ์: 8 (100์ log 2๋ฅผ ์ทจํ ๊ฐ)
5. ๋ง๋ฌด๋ฆฌ
- ์ด๋ค ๋ฌธ์ ๋ฅผ ํธ๋ ๋ฐฉ๋ฒ์ ๋๊ฐ ๋ ์ด์ ์กด์ฌํ๋ฉฐ, ์ฌ์ฉ์๊ฐ ์ ํํ๋ ์๊ณ ๋ฆฌ์ฆ์ด ์ฝ๋์ ์๋์ ํฌ๊ฒ ์ํฅ์ ์ค ์ ์๋ค.
- ์ ๋ ฌ๋ ๋ฐฐ์ด์ ๊ฒ์์ ๋งค์ฐ ํจ์จ์ ์ด์ง๋ง, ๊ฒ์์ด ์์ฃผ ํ์ํ์ง ์๊ณ , ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๊ธฐ๋ง ํ๋ค๋ฉด ์ฝ์ ์ ๋ ๋น ๋ฅด๊ฒ ์ฒ๋ฆฌํ๋ ๋ฐฐ์ด์ด ๋์ ์ ํ์ผ ์ ์๋ค.
- ์ฆ, ์ํฉ์ ๋ฐ๋ผ ์ด๋ค ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํํ๋๋๊ฐ ๊ธฐ๋์ ๊ฐ๋ฅธ๋ค.
'๐๏ธ ์ฑ & ๊ฐ์ ์ ๋ฆฌ > ๐๏ธ ๋๊ตฌ๋ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
6์ฅ ๊ธ์ ์ ์ธ ์๋๋ฆฌ์ค ์ต์ ํ (0) | 2022.11.04 |
---|---|
5์ฅ ๋น ์ค๋ฅผ ์ฌ์ฉํ๊ฑฐ๋ ์ฌ์ฉํ์ง ์๋ ์ฝ๋ ์ต์ ํ (0) | 2022.11.03 |
4์ฅ ๋น ์ค๋ก ์ฝ๋ ์๋ ์ฌ๋ฆฌ๊ธฐ (0) | 2022.11.02 |
3์ฅ ๋น ์ค ํ๊ธฐ๋ฒ (0) | 2022.10.29 |
1์ฅ ์๋ฃ๊ตฌ์กฐ๊ฐ ์ค์ํ ๊น๋ญ (0) | 2022.10.29 |