๐ฃ ์๋ก
2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ 1์ฐจ ์ฝ๋ฉ ํ ์คํธ ๋ฌธ์ ์์๊ฐ์ฌ ๊ฒ์ ๋ฌธ์ ๋ฅผ ํ์๋ค. ํ ์คํธ ์ผ์ด์ค๋ ์ ์์ ์ผ๋ก ๋์๊ฐ์ ์ ์ถ ํ๋๋ฐ ๋ต์ ๋ง์์ง๋ง ํจ์จ์ฑ ๋ถ๋ถ์์ 3๊ฐ๊ฐ ์๊ฐ ์ด๊ณผ๋์๋ค. ๋ฆฌํฉํ ๋ง์ ํ์ง๋ง ๊ฒฐ๊ณผ๋ ๊ฐ์๋ค.
์๊ฐ์ด ์ง๋๋ ๋์ ํ ์๊ฐ์ด ์๋์ํด์ค์ ๋ดค๋ค.
ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ ๋๋ ์ด๋ถ ํ์๋ฑ ๋ณด๋ค ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์ ์ด์ฉํด ์ฝ๋๋ฅผ ์์ฑํ ์ ์๋์ง ํ์
์๋ฃ๊ตฌ์กฐ์ ๋ํ ํ์ต์ด ๋ถ์กฑํ ํ์ธ์ง ํธ๋ผ์ด๋ ์ฒ์ ๋ค์ด๋ด์ ์ด๋ฒ ๊ธฐํ์ ์ ๋ฆฌํด๋ณด๋ ค๊ณ ํ๋ค.
๐ ํธ๋ผ์ด(Trie)๋?
๋ง์ ๋ฌธ์์ด ์ค์ ํน์ ๋ฌธ์๊ฐ ํฌํจ๋์ด ์๋์ง ๊ฒ์ํ๊ณ ์ถ์ผ๋ฉด, ํ๋์ฉ ๋น๊ตํ๋ฉด์ ์์๋ด๋ ๋ฐฉ๋ฒ์ด ์๋ค. ํ์ง๋ง ์ด๋ฌํ ๋ฐฉ๋ฒ์ ๋งค์ฐ ๋นํจ์จ์ ์ด๋ค. ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ๋ฉด ๋งค์ฐ ๋น ๋ฅธ ์๋๋ก ๋ฌธ์์ด์ ๊ฒ์ํ ์ ์๋ค. ๋ฌธ์์ด์ ์ต๋ ๊ธธ์ด๊ฐ M์ด๋ผ๊ณ ํ๋ฉด, O(M)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. ๋ฐ๋ผ์ ๋ค์ด๋ฒ์ ์๋ ์์ฑ ๊ธฐ๋ฅ๊ณผ ๊ฐ์ด ๋ฌธ์์ด์ ์ ์ฅ, ํ์ํ๋๋ฐ ์ ์ฉํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Retrieval ์์ ์ ๋๋์ด ํ๋ ๋ํจ์ด "Trie" ๋ผ๊ณ ์ด๋ฆ์ ๋ถ์๋ค.
๋ฐ์์ ํธ๋ผ์ด, ํธ๋ฆฌ ๋ ๊ฐ๋ค ์ฐ์ด๋๋ฐ "Tree" ์ ๋๊ฐ์ ๋ฐ์์ ๊ฐ์ง๊ณ ์์ด ๊ตฌ๋ถํ๊ธฐ ์ํด "ํธ๋ผ์ด" ๋ผ๊ณ ๋ถ๋ฆฌ๊ณ ์๋ค.
๐ ํธ๋ผ์ด(Trie)์ ๊ตฌ์กฐ
์ฌ์ ์์ "apple" ์ ์ฐพ์๋ณด๋ ค๋ฉด ์๋์ ๊ฐ์ ์์๋ก ์ฐพ์ ์ ์๋ค.
1. ๋งจ ์๊ธ์ 'a' ๋ก ์์ํ๋ ๋ถ๋ถ์ ์ฐพ๋๋ค. (a)
2. ๋ค์ 'p' ๋ก ์์ํ๋ ๋ถ๋ถ์ ์ฐพ๋๋ค. (ap)
3. ๋ค์ 'p' ๋ก ์์ํ๋ ๋ถ๋ถ์ ์ฐพ๋๋ค. (app)
4. ๋ค์ 'l' ๋ก ์์ํ๋ ๋ถ๋ถ์ ์ฐพ๋๋ค. (appl)
5. ๋ค์ 'e' ๋ก ์์ํ๋ ๋ถ๋ถ์ ์ฐพ๋๋ค. (apple)
๊ธฐ๋ณธ์ ์ผ๋ก K(๋ฌธ์์ด์ ๊ฐ์)์ง ํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๋ฉฐ, ์์ ๊ฐ์ด ๋ ผ๋ฆฌ์ ์ผ๋ก ์ปดํจํฐ์ ์ ์ฉํ ๊ฒ์ด ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ์ด๋ค.
๊ทธ๋ฆผ [1]์ ๋ณด๋ฉด app์ ๊ฒ์ํ์ ๋ 3๊ฐ์ ๋ฌธ์์ด(apple, appreciate, apply)์ด ๋์ค๊ฒ ๋๋๋ฐ ๋ฌธ์์ด์ ์ ์ฅํ๋ ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ณด๋ฉด ์์ ๊ฐ๋ค.
'Data Structure' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ ํธ๋ผ์ด(Trie) ์๋ฃ๊ตฌ์กฐ (0) | 2020.03.20 |
---|