[TIL๐Ÿ”ฅ]Day4(8/5)

dasssseulยท2021๋…„ 8์›” 5์ผ
0

Today I Learned

๋ชฉ๋ก ๋ณด๊ธฐ
4/22

Introduction

์˜ค๋Š˜๋„ ์‚ฌ์‹ค ๊ฐ•์˜๋Š” ๋งŽ์ด ๋“ฃ์ง€ ๋ชปํ–ˆ์ง€๋งŒ, ๊ทธ๋ž˜๋„ ์ด์ง„ ํŠธ๋ฆฌ ๊ตฌํ˜„๋„ ํ•ด๋ณด๊ณ  ๊ทธ๊ฑธ ์ด์šฉํ•ด์„œ ์ „์œ„, ์ค‘์œ„, ํ›„์œ„ ์ˆœํšŒ๋„ ์žฌ๊ท€ ํ•จ์ˆ˜ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•ด๋ณด์•˜๋‹ค.
๊ทธ๋ž˜๋„ ์กฐ๊ธˆ์”ฉ ์„ฑ์žฅํ•˜๋Š” ๊ฒƒ์„ ๋Š๋‚€๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํŒ€์›๋“ค์ด ๋งŽ์ด ๋„์™€์ค˜์„œ ๋„ˆ๋ฌด ๊ณ ๋ง™๋‹ค...๐Ÿ™Œ

์˜ค๋Š˜ ์ƒˆ๋กญ๊ฒŒ ๋ฐฐ์šด ๊ฒƒ

์˜ค๋Š˜๋„ ๊ณ„์†ํ•ด์„œ ์ž๋ฃŒ๊ตฌ์กฐ & ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐฐ์›Œ๋‚˜๊ฐ”๋‹ค.

1. ํŠธ๋ฆฌ(Tree)
2. ํž™(Heap)
3. ํŠธ๋ผ์ด(Trie)
4. ์ •๋ ฌ(Sort)

์‚ฌ์‹ค ๊ณ ๋ฐฑํ•˜์ž๋ฉด, ๋‹ค๋ฅธ ๊ฒƒ๋“ค์€ ๋Œ€๋ถ€๋ถ„ ํŒŒ์ด์ฌ์œผ๋กœ ์ ‘ํ•ด๋ดค์ง€๋งŒ ํŠธ๋ผ์ด๋Š” ์ฒ˜์Œ ์ ‘ํ•ด๋ดค๋‹ค... ๋‚˜์ž์‹  ๋ฐ˜์„ฑํ•ด๋ผ...

๊ทธ๋ž˜์„œ ์˜ค๋Š˜์€ ํŠธ๋ผ์ด์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๋ ค๊ณ  ํ•œ๋‹ค.

๐Ÿ“š ํŠธ๋ผ์ด(Trie)

ํŠธ๋ผ์ด(Trie)๋ž€?

  • ๋ฌธ์ž์—ด์„ ์ €์žฅํ•˜๊ณ  ํšจ์œจ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๊ธฐ ์œ„ํ•œ ํŠธ๋ฆฌ ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ

ํŠธ๋ผ์ด(Trie)์˜ ํŠน์ง•

  • ๊ฒ€์ƒ‰์–ด ์ž๋™ ์™„์„ฑ, ์‚ฌ์ „ ์ฐพ๊ธฐ ๋“ฑ์— ํ™œ์šฉ
  • ๋‹จ์ˆœ ๋น„๊ต๋ณด๋‹ค ํšจ์œจ์ ์œผ๋กœ ์ฐพ๊ธฐ๊ฐ€ ๊ฐ€๋Šฅ
  • L์ด ๋ฌธ์ž์—ด์˜ ๊ธธ์ด์ผ ๋•Œ ํƒ์ƒ‰, ์‚ฝ์ž…์€ O(L)๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค
  • ํ•˜์ง€๋งŒ, ๊ฐ ์ •์ ์ด ์ž์‹์— ๋Œ€ํ•œ ๋งํฌ๋ฅผ ์ „๋ถ€ ๊ฐ€์ง€๊ณ  ์žˆ์–ด ์ €์žฅ ๊ณต๊ฐ„์„ ๋งŽ์ด ์ฐจ์ง€ํ•œ๋‹ค

ํŠธ๋ผ์ด(Trie)์˜ ๊ตฌ์กฐ

  • ๋ฃจํŠธ๋Š” ๋น„์–ด์žˆ๋‹ค
  • ๊ฐ ๊ฐ„์„ ์€ ์ถ”๊ฐ€๋  ๋ฌธ์ž๋ฅผ ํ‚ค๋กœ ๊ฐ€์ง„๋‹ค
  • ๊ฐ ์ •์ ์€ ์ด์ „์˜ ์ •์ ์˜ ๊ฐ’ + ๊ฐ„์„ ์˜ ํ‚ค๋ฅผ ๊ฐ’์œผ๋กœ ๊ฐ€์ง„๋‹ค
  • ํ•ด์‹œ ํ…Œ์ด๋ธ”๊ณผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ ๊ฐ€๋Šฅ

Comment

์˜ค๋Š˜์€ ํŠธ๋ผ์ด์— ๋Œ€ํ•ด ๋ฐฐ์šฐ๊ณ  ์ด๋ฅผ ํ•ด์‹œ ํ…Œ์ด๋ธ”๋กœ ๊ตฌํ˜„ํ•ด๋ณด์•˜๋‹ค.
๋‚ด์ผ์€ ํŠธ๋ผ์ด๋ฅผ ์ด์šฉํ•ด ์ž๋™ ์™„์„ฑ ๊ธฐ๋Šฅ์„ ํ•œ๋ฒˆ ๊ตฌํ˜„ํ•ด๋ณด๊ณ ์žํ•œ๋‹ค.
์•„์ง ๊ฑฑ์ •๋งŒ ์•ž์„œ๊ธดํ•˜์ง€๋งŒ, ๊ทธ๋ž˜๋„ ๊ณ„์† ์‹œ๋„ํ•˜๋‹ค๋ณด๋ฉด ๊ผญ ์„ฑ๊ณตํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค.
ํ•ญ์ƒ ์‹คํŒจ๋ฅผ ๋‘๋ ค์›Œํ•˜์ง€ ์•Š๋Š” ์ž์„ธ๋ฅผ ๊ฐ–์ž! ๐Ÿ’ช

profile
์ธ์ƒ์€ ์šฉ๊ธฐ์˜ ์–‘์— ๋”ฐ๋ผ ์ค„์–ด๋“ค๊ฑฐ๋‚˜, ๋Š˜์–ด๋‚œ๋‹ค

0๊ฐœ์˜ ๋Œ“๊ธ€