ALGORITHMS · CHAPTER 02
기초 · 45분배열·연결 리스트·스택·큐
순서가 있는 데이터를 다루는 네 가지 방법
접근·삽입·삭제 조건에 따라 선형 자료구조를 선택한다.
CONCEPTS
개념을 문장으로 설명하기
배열
연속된 인덱스로 원소에 접근하는 자료구조입니다.
예시
arr[500]처럼 위치를 아는 접근은 빠르지만 중간 삽입은 뒤 원소를 밀 수 있습니다.
CHECK인덱스 접근 O(1)을 기억한다.
연결 리스트
노드가 다음 노드를 가리켜 순서를 만드는 구조입니다.
예시
삽입 위치 노드를 이미 알고 있으면 연결만 바꿔 빠르게 넣을 수 있습니다.
CHECK특정 위치 찾기는 O(n)이다.
스택·큐
스택은 LIFO, 큐는 FIFO 규칙으로 출입구를 제한한 선형 구조입니다.
예시
함수 호출은 스택, BFS의 방문 대기는 큐로 모델링합니다.
CHECK문제의 ‘순서 규칙’에서 고른다.
GUIDED PRACTICE
괄호 검사
문자열 '(()())'가 올바른 괄호인지 검사합니다.
- 여는 괄호를 만나면 스택에 push합니다.
- 닫는 괄호를 만나면 스택이 비어 있지 않은지 확인하고 pop합니다.
- 마지막에 스택이 비어 있으면 짝이 모두 맞습니다.
결론
스택의 ‘가장 최근에 연 것부터 닫는다’는 성질이 괄호 규칙과 정확히 맞습니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“배열”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“연결 리스트”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
문제의 ‘순서 규칙’에서 고른다.
04 · 풀이 재현
“괄호 검사”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
인덱스 100번째 원소에 접근하기 가장 유리한 구조는?
02
너비 우선 탐색의 다음 방문 후보를 관리하기 적합한 구조는?
03
되돌리기(Undo) 기능에 자연스러운 구조는?
SPEAK IT OUT
면접 1분 답변 연습
배열과 연결 리스트를 읽기·삽입·삭제 관점에서 비교하고, 각각의 사용 상황을 말해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Java SE · ArrayDeque원문 열기 ↗스택과 큐로 활용할 수 있는 표준 라이브러리 자료구조 문서입니다.