๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•
SMALL

Knowledge/Data structure3

[์ž๋ฃŒ๊ตฌ์กฐ]ํŒŒ์ด์ฌ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒ๊ตฌ์กฐ ์™„๋ฒฝ ๊ฐ€์ด๋“œ: ๊ธฐ์ดˆ๋ถ€ํ„ฐ ํ™œ์šฉ๊นŒ์ง€ ํŒŒ์ด์ฌ์—์„œ ๋ฐฐ์—ด์€ ์ž์ฃผ ์‚ฌ์šฉ๋˜์ง€๋งŒ, ๋” ๋ณต์žกํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ฅผ ํ•„์š”๋กœ ํ•  ๋•Œ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค. ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐ์ดํ„ฐ์˜ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๋ฉด์„œ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ์šฉ์ดํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ด ํฌ์ŠคํŒ…์—์„œ๋Š” ํŒŒ์ด์ฌ์œผ๋กœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๋‹จ๊ณ„๋ณ„๋กœ ์„ค๋ช…ํ•˜๊ณ , ๊ทธ ํ™œ์šฉ๋ฒ•์„ ์†Œ๊ฐœํ•ฉ๋‹ˆ๋‹ค.โ‰ฃ ๋ชฉ์ฐจ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ธฐ๋ณธ ๊ฐœ๋…๐Ÿ“˜ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ๋…ธ๋“œ ๊ตฌํ˜„๐Ÿ› ๏ธ ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌํ˜„๐Ÿ’ก ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌํ˜„๐Ÿ”„ ์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌํ˜„๐Ÿ” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ํ™œ์šฉ ์˜ˆ์ œ๐ŸŒ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์™€ ๊ด€๋ จ๋œ ๋ฌธ์ œ ํ•ด๊ฒฐ๐Ÿ” ํ•ต์‹ฌ ๋‚ด์šฉ๐Ÿ‘€01. ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ธฐ๋ณธ ๊ฐœ๋…๐Ÿ“˜์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๊ฐ ๋…ธ๋“œ๊ฐ€ ๋ฐ์ดํ„ฐ์™€ ๋‹ค์Œ ๋…ธ๋“œ์— ๋Œ€ํ•œ ์ฐธ์กฐ๋ฅผ ํฌํ•จํ•˜๋Š” ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ๋ฐฐ์—ด๊ณผ ๋‹ฌ๋ฆฌ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์—ฐ์†์ ์œผ๋กœ ์‚ฌ์šฉํ•  ํ•„์š”๊ฐ€ ์—†์–ด ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค... 2024. 7. 22.
[์ž๋ฃŒ๊ตฌ์กฐ]ํŒŒ์ด์ฌ ํ ์ž๋ฃŒ๊ตฌ์กฐ ์™„๋ฒฝ ๊ฐ€์ด๋“œ: ๊ธฐ๋ณธ ๊ฐœ๋…๋ถ€ํ„ฐ ์‹ค์ „ ํ™œ์šฉ๊นŒ์ง€ ํ(Queue)๋Š” ์ž๋ฃŒ๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹ ์ค‘ ํ•˜๋‚˜๋กœ, ๋จผ์ € ๋“ค์–ด์˜จ ๋ฐ์ดํ„ฐ๊ฐ€ ๋จผ์ € ๋‚˜๊ฐ€๋Š” ์„ ์ž…์„ ์ถœ(FIFO, First In First Out) ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ํ๋Š” ์ผ์ƒ์ƒํ™œ์—์„œ๋„ ๋งŽ์ด ๋ณผ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋กœ, ์˜ˆ๋ฅผ ๋“ค์–ด ์€ํ–‰์˜ ๋Œ€๊ธฐ ์ค„์ด ํ์˜ ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์ž…๋‹ˆ๋‹ค. ์ด๋ฒˆ ๊ธ€์—์„œ๋Š” ํŒŒ์ด์ฌ์—์„œ ํ๋ฅผ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•˜๊ณ  ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์ž์„ธํžˆ ์‚ดํŽด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.โ‰ฃ ๋ชฉ์ฐจํ ์ž๋ฃŒ๊ตฌ์กฐ๋ž€?๐Ÿ“šํ์˜ ์ฃผ์š” ์—ฐ์‚ฐ๐Ÿ”„ํ์˜ ์ข…๋ฅ˜๐ŸงฉํŒŒ์ด์ฌ์—์„œ ํ ๊ตฌํ˜„ ๋ฐฉ๋ฒ•๐Ÿ’ปํ์˜ ํ™œ์šฉ ์˜ˆ์‹œ๐Ÿ“Šํ์˜ ์žฅ๋‹จ์ โš–๏ธํ•ต์‹ฌ ๋‚ด์šฉ๐Ÿ‘€01. ํ ์ž๋ฃŒ๊ตฌ์กฐ๋ž€?๐Ÿ“šํ ์ž๋ฃŒ๊ตฌ์กฐ๋ž€ ๋ฌด์—‡์ธ๊ฐ€?ํ(Queue)๋Š” ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ ๋งค์šฐ ์ค‘์š”ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ํ•˜๋‚˜๋กœ, ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ  ๊ด€๋ฆฌํ•˜๋Š” ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. ํ๋Š” ์„ ์ž…์„ ์ถœ(FIFO, First In First Out) ๊ตฌ์กฐ.. 2024. 6. 19.
[์ž๋ฃŒ๊ตฌ์กฐ]ํŒŒ์ด์ฌ ์Šคํƒ ๊ตฌ์กฐ ์™„๋ฒฝ ๊ฐ€์ด๋“œ: ๊ฐœ๋…, ๊ตฌํ˜„ ๋ฐ ํ™œ์šฉ ์˜ˆ์ œ ํŒŒ์ด์ฌ์—์„œ ์Šคํƒ(Stack) ๊ตฌ์กฐ๋Š” ๋ฐ์ดํ„ฐ ์ €์žฅ ๋ฐ ์ ‘๊ทผ ๋ฐฉ์‹ ์ค‘ ํ•˜๋‚˜๋กœ, ํ›„์ž…์„ ์ถœ(LIFO: Last In, First Out) ์›์น™์„ ๋”ฐ๋ฆ…๋‹ˆ๋‹ค. ์ด๋Š” ๋งˆ์ง€๋ง‰์— ์ถ”๊ฐ€๋œ ํ•ญ๋ชฉ์ด ๊ฐ€์žฅ ๋จผ์ € ์ œ๊ฑฐ๋˜๋Š” ๊ตฌ์กฐ๋กœ, ๋ธŒ๋ผ์šฐ์ €์˜ ๋’ค๋กœ ๊ฐ€๊ธฐ ๊ธฐ๋Šฅ์ด๋‚˜ ํ˜ธ์ถœ ์Šคํƒ(Call Stack)์—์„œ ํ”ํžˆ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฒˆ ํฌ์ŠคํŒ…์—์„œ๋Š” ํŒŒ์ด์ฌ์—์„œ ์Šคํƒ ๊ตฌ์กฐ์˜ ๊ฐœ๋…, ๊ตฌํ˜„ ๋ฐฉ๋ฒ•, ๊ทธ๋ฆฌ๊ณ  ์‹ค์ „ ํ™œ์šฉ ์˜ˆ์ œ๋ฅผ ๋‹ค๋ฃฐ ๊ฒƒ์ž…๋‹ˆ๋‹ค.โ‰ฃ ๋ชฉ์ฐจ์Šคํƒ์ด๋ž€?๋ฐฐ์—ด๊ตฌ์กฐ๋กœ ์Šคํƒ ๊ตฌํ˜„ํ•˜๊ธฐ์Šคํƒ์˜ ํ™œ์šฉ ์˜ˆ์ œํŒŒ์ด์ฌ์—์„œ ์Šคํƒ ์‚ฌ์šฉํ•˜๊ธฐ์‹œ์Šคํ…œ์Šคํƒ๊ณผ ์ˆœํ™˜ํ˜ธ์ถœํ•ต์‹ฌ ๋‚ด์šฉ๐Ÿ‘€์Šคํƒ์€ ๋ฐฐ์—ด ๊ตฌ์กฐ๋กœ ๊ตฌํ˜„๋˜๋Š”๋ฐ, ํŒŒ์ด์ฌ์—์„œ๋Š” ๋ฐฐ์—ด์„ ๋ฆฌ์ŠคํŠธ์™€ ํŠœํ”Œ์„ ํ†ตํ•ด ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฐฐ์—ด์€ ์ž๋ฃŒ ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐ ํ•„์š”ํ•œ ์›์†Œ๋“ค์„ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•˜๋ฏ€๋กœ, ํŒŒ์ด์ฌ์—์„œ๋Š” ์ฃผ๋กœ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.. 2024. 6. 18.
728x90
๋ฐ˜์‘ํ˜•