๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Data Structure

๐Ÿ†ƒ ํŠธ๋ผ์ด(Trie) ์ž๋ฃŒ๊ตฌ์กฐ

๐Ÿ—ฃ ์„œ๋ก 

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] - ํŠธ๋ผ์ด ๊ตฌ์กฐ

๊ทธ๋ฆผ [1]์„ ๋ณด๋ฉด app์„ ๊ฒ€์ƒ‰ํ–ˆ์„ ๋•Œ 3๊ฐœ์˜ ๋ฌธ์ž์—ด(apple, appreciate, apply)์ด ๋‚˜์˜ค๊ฒŒ ๋˜๋Š”๋ฐ ๋ฌธ์ž์—ด์„ ์ €์žฅํ•˜๋Š” ํŠธ๋ผ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๋ณด๋ฉด ์œ„์™€ ๊ฐ™๋‹ค.

'Data Structure' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

๐Ÿ†ƒ ํŠธ๋ผ์ด(Trie) ์ž๋ฃŒ๊ตฌ์กฐ  (0) 2020.03.20