스택
Last In First Out
스택의 ADT
- 연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있기는 하지만 세부 구현 내용은 정의하고 있지 않음
문제 1
재귀가 없는 일반적인 상황을 가정해 봅시다. 함수 A가 함수 B를 호출하고, 함수 B가 함수 C를 호출했을 때, 컴퓨터 내부의 호출 스택(Call Stack) 에는 어떤 정보들이 어떤 순서로 쌓이고(Push) 해제(Pop)되는지 그 과정을 설명하세요. 이를 통해 호출 스택이 LIFO(Last-In, First-Out) 원리로 동작하는 이유를 서술하세요.
main -> A 호출 : 호출 스택에 A쌓임
A->B 호출 : 스택에 B 쌓임
B->C 호출 : 스택에 C 쌓임
PoP
C->B->A 순서
나중에 호출된 함수가 실행을 끝내야 이전 함수로 돌아갈 수 있다.
문제 2
재귀 함수는 자기 자신을 반복적으로 호출합니다. 재귀 함수가 호출될 때, 호출 스택은 재귀의 각 단계별 상태(매개변수, 지역 변수 등)를 어떻게 저장하고 복원하여 LIFO 원리에 따라 프로그램의 흐름을 관리하는지 설명하세요. 팩토리얼 계산과 같은 간단한 재귀 함수를 예시로 들어 구체적으로 서술하세요.
팩토리얼의 경우 호출 흐름(push)은 다음과 같다.
factorial(n) -> factorial(n-1) ... factorial(1)
pop 과정은
- factorial(1) 반환하고 pop
- factorial(2) 반환하고 pop
... - factorial(n) 반환하고 pop
문제 3
'짝이 맞는 괄호' 문제를 해결할 때 스택이 효과적인 이유는 무엇인가요? 스택의 LIFO(Last-In, First-Out) 원리가 괄호의 '중첩(nested)' 구조, 즉 '가장 안쪽에서 열린 괄호가 가장 먼저 닫혀야 한다'는 규칙을 어떻게 자연스럽게 처리할 수 있는지 그 핵심 원리를 논리적으로 설명하세요.
괄호는 가장 나중에 열린 괄호가 가장 먼저 닫혀야 한다.
LIFO는 가장 최근에 들어온 것부터 처리하기 때문에 가장 안쪽 괄호부터 처리한다는 논리와 일치한다.
- '('여는 괄호를 만나면 push
- ')'닫는 괄호를 만나면 pop
https://inf.run/Fymov
"코딩 테스트 합격자 되기 - 파이썬편 (박경록)"
