μ‹œλ„/ꡭ비지원

[D+09] 컴퓨터에선 λ©”λͺ¨λ¦¬λ₯Ό μ–΄λ–»κ²Œ μ‚¬μš©ν•˜λŠ”κ°€?

πŸ‡λ°•λ΄‰λ΄‰πŸ‡ 2022. 9. 30. 00:44

 

 

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μ—λŠ” 이름을 λΆ™μΌμˆ˜μ—†κΈ°λ•Œλ¬Έμ— μŠ€νƒμ˜μ—­μ— μ„ μ–Έν•œ λ³€μˆ˜μ΄λ¦„μ•ˆμ— λ°°μ—΄μ˜ μ‹œμž‘μ •λ³΄λ₯Ό λ‹΄μ•„μ„œ μœ„μΉ˜λ₯Ό μ•Œλ €μ£ΌλŠ” λ°©μ‹μœΌλ‘œ μ‚¬μš©λ˜κ³  μžˆλ‹€.

 

• 배열을 λ§Œλ“œλŠ” 방법

β‘  μ΄ˆκΈ°κ°’μ΄ μžˆλŠ” 경우

 

β‘‘ μ΄ˆκΈ°κ°’μ΄ μ—†λŠ” 경우

 

 

λ°˜μ‘ν˜•