๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์‹œ๋„/๊ตญ๋น„์ง€์›

[D+09] ์ปดํ“จํ„ฐ์—์„  ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์–ด๋–ป๊ฒŒ ์‚ฌ์šฉํ•˜๋Š”๊ฐ€?

by ๐Ÿ‡๋ฐ•๋ด‰๋ด‰๐Ÿ‡ 2022. 9. 30.

 

 

Algorithm

-  ์ปดํ“จํ„ฐ์—์„  ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์–ด๋–ป๊ฒŒ ์‚ฌ์šฉํ•˜๋Š”๊ฐ€? -

 


 

์ปดํ“จํ„ฐ์—์„  ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์–ด๋–ป๊ฒŒ ์‚ฌ์šฉํ•˜๋Š”๊ฐ€?

• ํ”„๋กœ์„ธ์Šค ๋ฉ”๋ชจ๋ฆฌ๋งต

- ์ผ๋ฐ˜์ ์ธ ์šด์˜์ฒด์ œ๊ฐ€ ํ”„๋กœ์„ธ์Šค๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ํ• ๋‹นํ•˜๋Š” ๊ตฌ์กฐ

- ํ”„๋กœ์„ธ์Šค๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ํ• ๋‹นํ•˜๋Š” ๋ฐฉ์‹์ด ๊ฐ ์šด์˜์ฒด์ œ๋งˆ๋‹ค ๋‹ค๋ฆ„.

 

์šด์˜์ฒด์ œ๋Š” ์ผ์ข…์˜ ๊ตฌ๋ถˆ๊ตฌ๋ถˆํ•œ ๊ธธ์„ ํ‰ํƒ„ํ™” ์ž‘์—…์„ ๊ฑฐ์ณ ํ‰ํ‰ํ•˜๊ฒŒ ๋งŒ๋“ค์–ด์ฃผ๋Š” ์—ญํ• ์„ ํ•œ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

• ๋ฉ”๋ชจ๋ฆฌ์˜ ๊ตฌ์กฐ

๋ฉ”๋ชจ๋ฆฌ์˜ ๊ตฌ์กฐ๋Š” ํฌ๊ฒŒ ์„ธ๊ฐ€์ง€๋กœ ๊ตฌ๋ถ„ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ๋ฐ”๋กœ ๊ธ€๋กœ๋ฒŒ์˜์—ญ, ํž™์˜์—ญ, ์Šคํƒ์˜์—ญ์ด๋‹ค.

์„ธ๊ฐ€์ง€๋กœ ๋‚˜๋‰œ์˜์—ญ์— ๊ฐ ํ”„๋กœ์„ธ์Šค๋Š” ํŠน์„ฑ์— ๋งž๊ฒŒ ๊ฐ์˜์—ญ์œผ๋กœ ๋‚˜๋ˆ ์„œ ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค.

 

• ๋ฉ”๋ชจ๋ฆฌ ๊ตฌ์กฐ - Stack ์˜์—ญ

- ์Šคํƒ์ด๋ž€ ๋™์ž‘ ๋งค๋„ˆ๋‹ˆ์ฆ˜์œผ๋กœ ๋™์ž‘๋ฐฉ์‹์„ ์˜๋ฏธํ•œ๋‹ค.

- ์ปดํŒŒ์ผ ํƒ€์ž„ Compile Time

- ํ•จ์ˆ˜๋‚ด์—์„œ ์ •์˜๋˜์–ด์ง€๋Š” ๋ณ€์ˆ˜์ธ ์ง€์—ญ๋ณ€์ˆ˜๊ฐ€ stack์˜์—ญ์— ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค. ex) ํ”„๋ฆฌ๋ฏธํ‹ฐ๋ธŒํƒ€์ž…, ์ฐธ์กฐํƒ€์ž…

- ๋ฐ์ดํ„ฐ๊ฐ€ ๋จผ์ € ๋“ค์–ด์˜จ๊ฒŒ ๋‚˜์ค‘์— ๋‚˜๊ฐ€๋Š” FILO(First In Last Out) ๊ตฌ์กฐ์ด๋‹ค.

- ํ•จ์ˆ˜ํ˜ธ์ถœ ๋ฐ ์ข…๋ฃŒ์˜ ๋™์ž‘๋ฐฉ์‹๊ณผ ์Šคํƒ์˜ ์šด์šฉ๋ฐฉ์‹์ด ์ผ์น˜ํ•œ๋‹ค.

- PUSHํ•˜๊ณ  POPํ•˜๋Š” ๊ณผ์ •์—์„œ ๋ฐ์ดํ„ฐ๊ฐ€ ๊พธ์ค€ํžˆ ๋ฐ”๋€๋‹ค.

 

์šฉ์–ด )

PUSH ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ฒƒ

POP ๋ฐ์ดํ„ฐ๋ฅผ ๋นผ๋Š”๊ฒƒ

SP(Stack Pointer) ์Šคํƒ์— POPํ•˜๊ฑฐ๋‚˜ PUSHํ•  ์œ„์น˜๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ํฌ์ธํ„ฐ

stack-overflow ์Šคํƒ์— ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฝ‰์ฐฌ ์ƒํƒœ

stack- underflow ์Šคํƒ์— ๋ฐ์ดํ„ฐ๊ฐ€ ๋น„์›Œ์ ธ ์žˆ๋Š” ์ƒํƒœ

 

• ๋ฉ”๋ชจ๋ฆฌ ๊ตฌ์กฐ - Global ์˜์—ญ

- ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ข…๋ฃŒํ• ๋•Œ ๊นŒ์ง€ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผํ• ๊ฒƒ์„ ๋‹ด๊ณ ์žˆ๋‹ค.

- ์ปดํŒŒ์ผ ํƒ€์ž„ Compile Time

- ๋ช…๋ น์–ด์ง‘ํ•ฉ(Instruction-SET) - ๋ช…๋ น์–ด ๋ชจ์Œ → ํ•จ์ˆ˜๋‹จ์œ„๋กœ ๋ชจ์—ฌ์žˆ๋‹ค.

- ๋ฆฌํ„ฐ๋Ÿด - ์†Œ์Šค์ฝ”๋“œ์—์„œ ์‚ฌ์šฉํ•˜๋Š” ๊ฐ์ข… ๊ฐ’๋“ค

- ์ „์—ญํ™” ์ง€์—ญ๋ณ€์ˆ˜(static)

 

• ๋ฉ”๋ชจ๋ฆฌ ๊ตฌ์กฐ - Heap ์˜์—ญ

- new๋กœ ํ• ๋‹นํ•œ ๋ฉ”๋ชจ๋ฆฌ ๋ธ”๋ก

- ๋Ÿฐํƒ€์ž„ Run Time

- ํž™์˜์—ญ์€ ์–ธ์ œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ƒ์„ฑ๋ ์ง€ ์•ˆ๋ ์ง€ ๋ชจ๋ฅด๊ธฐ ๋–„๋ฌธ์— ๋ณ€์ˆ˜์˜ ์ด๋ฆ„์„ ๋”ฐ๋กœ ๋ถ™์ผ ์ˆ˜๊ฐ€ ์—†๋‹ค.

   → ์ด๋ฆ„์„ ๋”ฐ๋กœ ๋ถ™์ผ ์ˆ˜ ์—†์ง€๋งŒ ์‹œ์ž‘์œ„์น˜์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

   → ์ด๋•Œ์˜ ์‹œ์ž‘์ •๋ณด์œ„์น˜์ธ ๋ž˜ํผ๋Ÿฐ์Šค ๊ฐ’์€ ํž™์— ๋“ค์–ด๊ฐ€๋Š” ๋ฐ์ดํ„ฐํฌ๊ธฐ์— ์ƒ๊ด€์—†์ด ๋™์ผํ•˜๋‹ค.

- ์ง์ ‘์ ‘๊ทผ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜์—ฌ ์ฐธ์กฐ๋ณ€์ˆ˜(=๋ž˜ํผ๋Ÿฐ์Šค๋ณ€์ˆ˜)๋ฅผ ํ†ตํ•ด ์ ‘๊ทผํ•œ๋‹ค.

- ํž™์˜์—ญ์€ ์–ด๋–ค ๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ๊ฐ€ ๋“ค์–ด์˜ฌ์ง€ ๋ชจ๋ฅด๊ธฐ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ๊ตฌ์กฐ์—์„œ ๊ฐ€๋Šฅํ•œ ํฌ๊ฒŒ ํ• ๋‹นํ•œ๋‹ค.

 

• ๋ฐฐ์—ด(Array)

- ์–ด๋–ค Data-type์„ T๋ผ๊ณ  ํ•  ๋•Œ, T๊ฐ€ n๊ฐœ ์—ฐ์†ํ•˜์—ฌ ํ• ๋‹น๋œ ์ž๋ฃŒ๊ตฌ์กฐ

- ๋ฐฐ์—ด์˜ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚˜๊ฑฐ๋‚˜ ์ค„์–ด๋“ค ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— Runtime ํ˜•์‹์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค.

- ๋ฐฐ์—ด์€ Heap์˜์—ญ์— ๋“ค์–ด๊ฐ€๊ฒŒ ๋˜๋Š”๋ฐ Heap์—๋Š” ์ด๋ฆ„์„ ๋ถ™์ผ์ˆ˜์—†๊ธฐ๋•Œ๋ฌธ์— ์Šคํƒ์˜์—ญ์— ์„ ์–ธํ•œ ๋ณ€์ˆ˜์ด๋ฆ„์•ˆ์— ๋ฐฐ์—ด์˜ ์‹œ์ž‘์ •๋ณด๋ฅผ ๋‹ด์•„์„œ ์œ„์น˜๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ์‚ฌ์šฉ๋˜๊ณ  ์žˆ๋‹ค.

 

• ๋ฐฐ์—ด์„ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•

โ‘  ์ดˆ๊ธฐ๊ฐ’์ด ์žˆ๋Š” ๊ฒฝ์šฐ

 

โ‘ก ์ดˆ๊ธฐ๊ฐ’์ด ์—†๋Š” ๊ฒฝ์šฐ

 

 

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€