이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 기초 자료구조
LIFO/FIFO principles, array/linked list implementations, bracket matching, BFS, deque, circular queue, priority queue preview, and monotone stack.
오늘은 스택과 큐를 깊이 있게 배워볼 거예요.
먼저 스택부터 시작합니다.
스택은 Last In First Out — 마지막에 넣은 것이 먼저 나오는 구조예요.
그림 왼쪽을 보세요 — 접시가 차곡차곡 쌓여 있어요.
접시 D가 가장 위에 있죠? 꺼낼 때도 D부터 꺼내야 해요.
이게 바로 LIFO — 마지막에 올린 접시가 먼저 나옵니다.
가운데 박스를 보면 핵심 연산 네 가지가 있어요.
push는 top 위에 새 원소를 추가해요 — O(1)이에요.
pop은 top 원소를 제거하고 반환해요 — 역시 O(1)이에요.
peek은 제거 없이 top을 확인만 하고, isEmpty는 비었는지 확인합니다.
네 연산 모두 O(1)이에요 — 왜일까요?
스택은 오직 top에서만 작업하니까 원소가 몇 개든 상관없어요.
오른쪽을 보면 스택이 강력한 이유가 정리되어 있어요.
제한된 인터페이스가 오히려 실수를 방지해요.
Ctrl+Z를 누르면 가장 최근 작업이 취소되죠? 그게 바로 pop이에요!
함수 호출, 괄호 검사, DFS — 모두 스택이 핵심이에요.
배열처럼 아무 위치나 접근하는 것보다 top만 쓰는 게 더 안전해요.
적을수록 강하다 — 이것이 스택의 철학이에요.
다음 슬라이드에서 스택의 실제 구현을 코드로 살펴봅시다.
배열과 연결 리스트, 어떤 게 더 나을까요?
선생님: 스택에서 pop을 할 때 스택이 비어있으면 어떻게 될까요?
학생: 음... 에러가 나겠죠? 빈 스택에서 꺼낼 게 없으니까요.
선생님: 맞아요! 그래서 pop 전에 항상 isEmpty를 확인하거나 예외 처리를 해야 해요.
학생: 그러면 peek도 빈 스택이면 에러인가요?
선생님: 네, 같은 이유예요. 실전에서는 if문으로 비어있는지 먼저 체크하는 게 좋은 습관이에요.
학생: 스택에 중간 원소를 접근하고 싶으면 어떻게 하나요?
선생님: 원칙적으로는 불가능해요. 중간까지 pop해야 하는데, 그러면 스택의 장점을 잃어요. 중간 접근이 필요하면 배열을 쓰는 게 맞아요.