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

๐Ÿค– data structures & algorithms

Data Structures & Algorithms with Javascript : ์ค‘๊ฐ„(?) ์ ๊ฒ€ ๐Ÿช

[์ด์ „๊ธ€] 2024.07.25 - [๐Ÿค– data structures & algorithms] - Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

 

Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

2024.07.24 - [๐Ÿค– data structures & algorithms] - Data Structures & Algorithms with Javascript : Sets Data Structures & Algorithms with Javascript : Sets[์ด์ „ ๊ธ€]2024.07.23 - [๐Ÿค– data structures & algorithms] - Data Structures & Algorithms with Java

pyotato-dev.tistory.com

 

์ด์ œ Data Structures & Algorithms with Javascript ์„ 4 ๋‹จ์› ์ •๋„ ๋‚จ๊ฒจ๋‘๊ณ  ์žˆ๋Š” ์‹œ์ ์ด๋‹ค.

ํšŒ๊ณ ๋ผ๊ณ  ํ•˜๊ธฐ์—” ์ด๋ฅด์ง€๋งŒ ํ•œ๋ฒˆ ์ค‘๊ฐ„ ์ ๊ฒ€ ๊ฒธ ๋А๋‚€ ์ ๊ณผ ์ƒ๊ฐ๋“ค์„ ๊ธฐ๋กํ•ด๋ณด๊ณ ์ž ํ•œ๋‹ค.

์ด ์ฑ…์„ ์ถ”์ฒœํ•œ๋‹ค?

๐Ÿ˜“ ์ด๋Ÿฐ ์ ์€ ์ฝ๋Š”๋ฐ ๋ถˆํŽธํ–ˆ์–ด์š”!

์ ˆํŒ์ด ๋˜์–ด ํ˜„์žฌ๋Š” pdf ์›์„œ๋ฅผ ์ฝ๊ณ  ์žˆ๋‹ค. ์ž๋ฃŒ ๊ตฌ์กฐ์— ๋Œ€ํ•ด ๊ณต๋ถ€๋ฅผ ํ•ด๋ดค์ง€๋งŒ, ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ๋กœ ๋‹ค๋ฃฌ ๊ฑด ์ฒ˜์Œ์ด์—ˆ๊ณ , ์ ๊ฒ€ ๊ฒธ ์ถ”์ฒœ์„ ๋ฐ›์•„์„œ ์ฝ์–ด๋ณด๊ธฐ๋กœ ํ–ˆ์—ˆ๋‹ค. ์•„์‰ฌ์šด ์ ์€ ์ด ์ฑ…์ด 2014๋…„์— ์ถœํŒ๋˜์–ด์„œ ์ตœ์‹  JS ๋ฌธ๋ฒ•์„ ํ™œ์šฉํ•˜๊ณ  ์žˆ์ง€ ๋ชปํ•˜๋‹ค๋Š” ์ , ๊ทธ๋ฆฌ๊ณ  ์˜ˆ์ œ์—์„œ ๋‹ค๋ฃฌ ์ฝ”๋“œ๊ฐ€ ์ผ๋ถ€ ๋™์ž‘์ด ์ž˜ํ•˜์ง€ ์•Š๊ฑฐ๋‚˜ ํ•จ์ˆ˜๋ฅผ ์„ ์–ธํ•œ ๋ถ€๋ถ„์„ ์ƒ๋žตํ•ด์„œ ์œ ์‚ฌํ•˜๊ฒŒ ๋Œ€์ฒด๋ฅผ ํ•ด์•ผ ํ–ˆ๋˜ ์ ์ด ์žˆ๋‹ค. 

 

๐Ÿค— ์ด๋Ÿฐ ์ ์€ ์ฝ๋Š”๋ฐ ๋„์›€์ด ๋˜์—ˆ์–ด์š”!

์ข‹์•˜๋˜ ์ ์€ ์•„์ฃผ ์ฝ๊ธฐ ์‰ฝ๊ฒŒ ์ž๋ฃŒ ๊ตฌ์กฐ์— ๋Œ€ํ•ด ์„ค๋ช…์„ ํ–ˆ๊ณ , ํ•จ์ˆ˜๋กœ ์ž‘์„ฑ๋œ ์ฝ”๋“œ์ง€๋งŒ ํด๋ž˜์Šค ๋ฌธ๋ฒ•์œผ๋กœ ์ „ํ™˜ํ•˜๋Š”๋ฐ ์–ด๋ ค์›€์ด ์ „ํ˜€ ์—†์–ด์„œ ํ•จ์ˆ˜๊ฐ€ ์ผ๊ธ‰ ๊ฐ์ฒด์ธ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์˜ ํŠน์ง•์ด ์ž˜ ๋А๋‚„ ์ˆ˜ ์žˆ์—ˆ๋‹ค.  ํด๋ž˜์Šค ๋ฌธ๋ฒ•์ด ์ต์ˆ™ํ•˜์ง€ ์•Š์€ ์‚ฌ๋žŒ๋“ค์—๊ฒŒ๋Š” ์˜คํžˆ๋ ค ํ•จ์ˆ˜๋กœ ์ž‘์„ฑ๋œ ์ฝ”๋“œ๋ฅผ ํด๋ž˜์Šค๋กœ ๊ตฌํ˜„ํ•ด ๋ณด๋ฉด์„œ ์—ฐ์Šต์„ ํ•˜๊ธฐ ์ข‹์€ ๊ฒƒ๋„ ์žˆ๋‹ค.

 

์–ด๋ ค์šด ๊ธฐ์ˆ ์ ์ธ ๋ถ€๋ถ„์€ ์ƒ๋žตํ•ด์„œ ์ •๋ง ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„์— ์ดˆ์ ์„ ๋งž์ถœ ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์—์„œ ์ข‹์•˜๋‹ค. 

์˜ˆ๋ฅผ ๋“ค๋ฉด, 8์žฅ์— ํ•ด์‰ฌ์— ๋Œ€ํ•ด์„œ ๋‹ค๋ฃจ๋Š”๋ฐ ํ•ด์‰ฌ function์„ ๊ตฌํ˜„ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜(Horner's method)์˜ ์ˆ˜ํ•™์ ์ธ ๋ถ€๋ถ„์— ์ดˆ์ ์„ ๋งž์ถ”๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” ์–ด๋–ป๊ฒŒ ํ™œ์šฉํ•ด์„œ ์‚ฌ์šฉํ•˜์ง€ ์•Š์•˜์„ ๊ฒฝ์šฐ ๋Œ€๋น„ ์žฅ์ ์„ ๋ถ€๊ฐํ•œ๋‹ค. ๊ถ๊ธˆํ•˜๋ฉด ๋š๋”ฑ ๊ตฌ๊ธ€๋งํ•  chatgpt์—๊ฒŒ ๋ฌผ์–ด๋ณผ ์ˆ˜ ์žˆ์ง€๋งŒ, ์ข…์ข… ๊ทธ๋Ÿฐ ํ† ๋ผ๊ตด์— ํ˜„ํ˜น๋ผ์„œ ๊ธธ ์žƒ๋Š” ๋‚˜๊ฐ™์€ ๋…์ž๋“ค์„ ๋ฐฐ๋ คํ•ด ์ค€ ๊ฑฐ ๊ฐ™์•„์„œ ์žฅ์ ์œผ๋กœ ๋‹ค๊ฐ€์˜จ๋‹ค. 

 

ํ•ญ์ƒ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ˆœํšŒ ๋ฐฉ์‹์„ ๋‹ฌ๋‹ฌ ์™ธ์šฐ๊ณ  ์žˆ์—ˆ๋Š”๋ฐ ์˜ˆ์ œ๋ฅผ ํ†ตํ•ด ์–ด๋–ป๊ฒŒ ๋™์ž‘ํ• ์ง€ ์ƒ๊ฐํ•ด ๋ณด๊ณ  ์ฝ”๋“œ๋ฅผ ์งค ์ˆ˜ ์žˆ์–ด์„œ ์ข‹์•˜๋‹ค. ๋‹จ์›๋“ค์„ ๊ธฐ์ค€์œผ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ž๋ฃŒ ๊ตฌ์กฐ์— ๋Œ€ํ•œ ํ‹€์„ ์žก๊ธฐ ์ข‹์€ ์ฑ…์ด๊ธฐ๋„ ํ•˜๋‹ค.

inorder preorder postorder bst traversal

 

์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋Œ€ํ•œ ๊ณต๋ถ€๋ฅผ ํ•œ๋ฒˆ ํ•ด๋ดค๋Š”๋ฐ ์ •๋ฆฌ๋ฅผ ํ•ด๋ณด๊ณ  ์‹ถ๊ฑฐ๋‚˜, ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ๋กœ ์ฝ”๋“œ๋ฅผ ์งœ๋ณด๊ณ  ์‹ถ์€ ์‚ฌ๋žŒ๋“ค์—๊ฒŒ ํ•œ ๋ฒˆ์ฏค ์ฝ์–ด๋ณผ ๋งŒํ•œ ์ฑ…์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฑฐ ๊ฐ™๋‹ค. 

 

์ฝ๊ธฐ ์ „๊ณผ ํ˜„์žฌ ์ฝ๊ณ  ์žˆ๋Š” ์‹œ์ ์˜ ์ƒ๊ฐ ๋ณ€ํ™”

์ฝ๊ธฐ์ „ ์—๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ž๋ฃŒ ๊ตฌ์กฐ๋ฅผ ์ง์ ‘ ์œ ์šฉํ•˜๊ฒŒ ์“ฐ์ผ ์‹œ๋‚˜๋ฆฌ์˜ค๋ฅผ ํฌ๊ฒŒ ๊ธฐ๋Œ€ํ–ˆ๋˜ ๊ฑฐ ๊ฐ™๋‹ค.

ํ•˜์ง€๋งŒ ํ˜„์žฌ๋Š” ์•ฝ๊ฐ„ ๊ธฐ๋ณธ๊ธฐ ์ ๊ฒ€์„ ํ•˜๋Š” ๋А๋‚Œ์œผ๋กœ ์ฑ…์„ ์ฝ๊ณ  ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด์ „์— ๊ณต๋ถ€ํ–ˆ๋˜ ๊ฒƒ๋“ค์ด ์ƒˆ๋ก์ƒˆ๋ก ์ƒ๊ฐ๋‚˜์„œ ๋‹ค์‹œ ์ •๋ฆฌ๋ฅผ ํ•ด๋ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ๋„ ๋“ค์—ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์—”์ง„ ์ตœ์ ํ™”์— ๋Œ€ํ•ด ์ด์ „์— ๊ณต๋ถ€ํ•œ ์ ์ด ์žˆ์—ˆ๋Š”๋ฐ, v8 ์—”์ง„์œผ๋กœ ๋Œ์•„๊ฐ€๋Š” ํฌ๋กฌ ๋ธŒ๋ผ์šฐ์ €์—์„œ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์ฝ”๋“œ๋กœ ๋ฐฐ์—ด ์ตœ์ ํ™”ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, ๋ฐฐ์—ด์„ ์–ด๋–ค ์‹์œผ๋กœ ๋‹ค๋ค„์•ผ ํ•˜๋Š”์ง€ ๊ณต๋ถ€ํ–ˆ๋˜ ๊ฒƒ์ด ๊ฐ€๋ฌผ๊ฐ€๋ฌผํ•ด์„œ ๋‹ค์‹œ ์‚ดํŽด๋ด์•ผ ํ•  ๊ฑฐ ๊ฐ™๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

 

์ง€๊ธˆ์€ ๊ฐ€๋ฌผ๊ฐ€๋ฌผํ•œ๋ฐ ๊ตฌ๊ธ€์˜ ์˜์ƒ์—์„œ ์ตœ์ ํ™” ๋“์„ ๋ณด๋ ค๋ฉด ๋ฐฐ์—ด์„ ์„ ์–ธํ•  ๋•Œ ํ†ต์ผ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•ด์•ผ ํžˆ๋“  ํด๋ž˜์Šค๋ฅผ ์จ๋จน์„ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฑธ ๋– ์˜ฌ๋ž๋‹ค. ์ด ์ฑ…์—์„œ๋„ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ๋ฐฐ์—ด์€ ์ž๋ฐ”๋‚˜ c++์—์„œ ๋ณด๋Š” ๋ฐฐ์—ด๊ณผ๋Š” ๋‹ฌ๋ฆฌ ๊ฐ์ฒด๋ผ๋Š” ์ ์„ ์–ธ๊ธ‰ํ–ˆ๋‹ค.

๊ฐ‘์ž๊ธฐ "์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ๋ฐฐ์—ด๋„ ๊ฐ์ฒด๋‹ค"์—์„œ ์—„์ฒญ ๋œฌ๊ธˆ์—†๋Š” ์ƒ๊ฐ๊นŒ์ง€ ๋ป—์–ด์™”๋‹ค๊ณ  ์ƒ๊ฐ์ด ๋“ค ์ˆ˜๋„ ์žˆ์ง€๋งŒ, ๋ฒ ์ด์Šค ๋ถ€๋ถ„์—์„œ๋„ ์ด์ „์— ๊ณต๋ถ€ํ–ˆ๋˜ ๊ฒƒ๋“ค์„ ๋– ์˜ฌ๋ฆฌ๊ฒŒ ํ•ด ์ค˜์„œ ์ข‹์€ ์ฑ…์ธ ๊ฑฐ ๊ฐ™๋‹ค. 

 

๋‹ค๋งŒ ์ด ์ฑ…์ด ๋” ๊นŠ์ด ์žˆ๋Š” ๊ฒƒ์„ ํŒŒ๊ณ ๋“ค๋ฉฐ ์‚ดํŽด๋ด์•ผ ํ•˜๋Š” ์˜์—ญ์€ ๋‹ค๋ฃจ์ง€ ๋ชปํ•ด์„œ ์ข€ ์•„์‰ฌ์šด ์ ์€ ์žˆ๋‹ค. 

๊ทธ ๋ถ€๋ถ„์— ๋Œ€ํ•ด์„œ๋Š” ์ฑ… ์™„๋… ํ›„ ๋” ๋‚œ์ด๋„ ์žˆ๋Š” ์ฑ…๋“ค์„ ์‚ดํŽด๋ณด๊ฑฐ๋‚˜, ์ด์ „ ๊ณต๋ถ€ํ•ด ๋ดค๋˜ ๊ฒƒ๋“ค ์ค‘ ๊ธฐ์–ต์ด ํ๋ฆฟํ•ด์ง„ ๊ฒƒ๋“ค์„ ๋‹ค์‹œ ํŒŒ๋ด์•ผ๊ฒ ๋‹ค.

 

ํ•˜๋ฃจ 1๋‹จ์›์”ฉ ์ฝ์–ด์™”๋Š”๋ฐ, ์ด์ œ 3-4์ผ ์ด๋ฉด ์™„๋…! ๐Ÿฅณ