2024. 10. 25. 08:39ใ์๋ฃ๊ตฌ์กฐ
๐๋ค์์ ์๋ฃ(Data)๋ฅผ ๋ด๊ธฐ ์ํ ๊ตฌ์กฐ
์๋ฃ๊ตฌ์กฐ์ ํ์์ฑ์ ๋ํด์ ์ดํดํ ํ์๊ฐ ์๋ค
์ฑ๋ฅ๋น๊ต: ์๋ฃ๊ตฌ์กฐ/์๊ณ ๋ฆฌ์ฆ์ ์ฑ๋ฅ ์ธก์ ๋ฐฉ๋ฒ์ ๋ํด ์ดํดํ ํ์๊ฐ ์๋ค.
์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ๋๋ก ์ดํดํ์ง ๋ชปํ๋ฉด ๋ถํ์ํ๊ฒ ๋ฉ๋ชจ๋ฆฌ์ ๊ณ์ฐ์ ๋ญ๋นํ๋ค.
๐์ ํ ๊ตฌ์กฐ
ํ๋์ ๋ฐ์ดํฐ ๋ค์ ๋ค๋ฅธ ๋ฐ์ดํฐ๊ฐ ํ๋ ์กด์ฌํ๋ ์๋ฃ๊ตฌ์กฐ
๋ฐ์ดํฐ๊ฐ ์ผ๋ ฌ๋ก ์ฐ์์ ์ผ๋ก(์์ฐจ์ ์ผ๋ก) ์ฐ๊ฒฐ๋์ด ์๋ค.
- ๋ฐฐ์ด
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ (linked list)
- ์คํ
- ํ, ๋ฑ(deque)
๐๋น์ ํ ๊ตฌ์กฐ
ํ๋์ ๋ฐ์ดํฐ ๋ค์ ๋ค๋ฅธ ๋ฐ์ดํฐ๊ฐ ์ฌ๋ฌ ๊ฐ ์ฌ ์ ์๋ ์๋ฃ๊ตฌ์กฐ
๋ฐ์ดํฐ๊ฐ ์ผ์ง์ ์์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ง ์์๋ ๋๋ค
- ํธ๋ฆฌ
- ๊ทธ๋ํ (BFS, DFS ๋ฑ)
๋ฌธ์ ์ํฉ์ ๋ง๋ ์ ์ ํ ์๋ฃ๊ตฌ์กฐ๊ฐ ์ฌ์ฉ๋์ด์ผ ํ๋ค.
์๊ฐ ๋ณต์ก๋
- ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉ๋๋ ์ฐ์ ํ์๋ฅผ ์ธก์ ํ๋ค.
๊ณต๊ฐ ๋ณต์ก๋
- ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉ๋๋ ๋ฉ๋ชจ๋ฆฌ์ ์์ ์ธก์ ํ๋ค.
๊ณต๊ฐ์ ๋ง์ด ์ฌ์ฉํ๋ ๋์ ์๊ฐ์ ๋จ์ถํ๋ ๋ฐฉ๋ฒ์ด ํํ ์ฌ์ฉ๋๋ค.
๐ํ๋ก๊ทธ๋จ์ ์ฑ๋ฅ ์ธก์ ๋ฐฉ๋ฒ: Big-O ํ๊ธฐ๋ฒ
- ํน์ ํ ์๊ณ ๋ฆฌ์ฆ์ด ์ผ๋ง๋ ํจ์จ์ ์ธ์ง ์์น์ ์ผ๋ก ํํํ ์ ์๋ค.
- ๊ฐ์ฅ ๋น ๋ฅด๊ฒ ์ฆ๊ฐํ๋ ํญ๋ง์ ๊ณ ๋ คํ๋ ํ๊ธฐ๋ฒ
ํ์ค์์๋ ๋์ ์๊ฐ์ด 1์ด ์ด๋ด์ธ ์๊ณ ๋ฆฌ์ฆ์ ์ค๊ณํ ํ์๊ฐ ์๋ค.
Big-O ํ๊ธฐ๋ฒ์ผ๋ก ์๊ฐ ๋ณต์ก๋๋ฅผ ํ๊ธฐํ ๋๋ ๊ฐ์ฅ ํฐ ํญ๋ง์ ํ์ํ๋ค.
์ฝ๋ฉ ํ ์คํธ์์ ๋ฉ๋ชจ๋ฆฌ์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ผ ๋๋ ์ผ๋ฐ์ ์ผ๋ก MB๋จ์๋ก ํ๊ธฐํ๋ค.
์ถ์ฒ: https://fastcampus.co.kr/dev_online_upjscodingtest ,https://en.wihipedia.org/wiki/Big_O_notation
'์๋ฃ๊ตฌ์กฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] ํธ๋ฆฌ(Tree)์ ์ฐ์ ์์ ํ(Priority Queue) (2) | 2024.10.27 |
---|---|
[์๋ฃ๊ตฌ์กฐ] ํ(Queue) (1) | 2024.10.27 |
[์๋ฃ๊ตฌ์กฐ] ์คํ(Stack) (0) | 2024.10.27 |
[์๋ฃ๊ตฌ์กฐ] ๋ฐฐ์ด(Array)๊ณผ ๋ฆฌ์คํธ(List) (0) | 2024.10.27 |
[์๋ฃ๊ตฌ์กฐ] Linked List (์ฐ๊ฒฐ ๋ฆฌ์คํธ) - ๋จ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ (0) | 2023.06.21 |