정보처리기사 · 소프트웨어 개발 과목
정보처리기사 자료구조와 알고리즘 개념 정리
중요도 ★★★★★ · 40% (추정)
AI가 새로 쓴 글 가운데, 작성과 분리된 AI 검증(다시 읽고 사실·수치 확인)을 통과한 단원만 싣습니다. 틀린 곳을 발견하면 알려 주세요.
핵심 개념
스택
나중에 넣은 자료가 먼저 나오는(LIFO) 자료구조입니다. 넣는 것을 push, 꺼내는 것을 pop 이라 합니다.
외우는 요령접시 쌓기 — 맨 위 접시부터 꺼냅니다.
큐
먼저 넣은 자료가 먼저 나오는(FIFO) 자료구조입니다. 한쪽 끝에서 넣고 반대쪽 끝에서 꺼냅니다.
외우는 요령은행 번호표 줄 — 먼저 온 사람이 먼저.
트리 순회
전위 순회는 뿌리 → 왼쪽 → 오른쪽, 중위 순회는 왼쪽 → 뿌리 → 오른쪽, 후위 순회는 왼쪽 → 오른쪽 → 뿌리 순서로 방문합니다.
외우는 요령'뿌리가 앞(전) – 가운데(중) – 뒤(후)'.
정렬의 시간 복잡도
버블·선택·삽입 정렬은 평균 O(n²) 이고, 퀵·병합·힙 정렬은 평균 O(n log n) 입니다.
외우는 요령이름이 쉬운 정렬(버블·선택·삽입)은 느리다고 기억하세요.
이진 검색
정렬된 자료의 가운데 값과 비교해 찾는 범위를 절반씩 줄이는 검색 방법입니다. 시간 복잡도는 O(log n) 입니다.
외우는 요령'반씩 자른다' — 반드시 정렬되어 있어야 합니다.
자주 나오는 포인트
- 스택과 큐(LIFO·FIFO)를 구분하는 문제가 가장 기본입니다.
- 트리를 주고 전위·중위·후위 순회 결과를 묻는 문제가 자주 나옵니다.
- 정렬 알고리즘의 시간 복잡도를 짝짓는 문제가 나옵니다.
헷갈리는 것 비교: 스택과 큐
| 구분 | 스택 | 큐 |
|---|---|---|
| 나오는 순서 | 나중에 넣은 것 먼저(LIFO) | 먼저 넣은 것 먼저(FIFO) |
| 예 | 접시 쌓기, 되돌리기 기능 | 줄 서기, 인쇄 대기열 |
대표 문제 3개
검수를 마친 예상문제 가운데 이 단원의 대표 문제입니다.
문제 1. 먼저 넣은 자료가 먼저 나오는 선입선출(FIFO) 구조의 자료구조는?
- ① 큐(Queue)
- ② 트리(Tree)
- ③ 그래프(Graph)
- ④ 스택(Stack)
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ① 큐(Queue)
핵심: 큐는 FIFO, 스택은 LIFO
큐는 줄 서기와 같습니다. 한쪽 끝(rear)으로 넣고 반대쪽 끝(front)으로 꺼내므로 먼저 들어온 것이 먼저 나갑니다.
틀린 선지
- ② 트리(Tree): 부모와 자식으로 이어진 계층 구조입니다.
- ③ 그래프(Graph): 정점과 간선으로 이루어진 구조입니다.
- ④ 스택(Stack): 나중에 넣은 자료가 먼저 나오는 후입선출(LIFO) 구조입니다.
문제 2. 스택(Stack)에 대한 설명으로 옳은 것은?
- ① 먼저 넣은 자료가 먼저 나오는 선입선출(FIFO) 구조이다.
- ② 나중에 넣은 자료가 먼저 나오는 후입선출(LIFO) 구조이다.
- ③ 양쪽 끝에서 모두 넣고 뺄 수 있다.
- ④ 운영체제의 작업 스케줄링에 주로 쓰인다.
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ② 나중에 넣은 자료가 먼저 나오는 후입선출(LIFO) 구조이다.
핵심: 스택은 LIFO(후입선출), 큐는 FIFO(선입선출)
스택은 접시를 쌓는 것과 같아서 맨 위(나중에 올린 것)부터 꺼냅니다. 함수 호출, 되돌리기(Undo), 괄호 검사에 쓰입니다.
틀린 선지
- ① 먼저 넣은 자료가 먼저 나오는 선입선출(FIFO) 구조이다.: 큐의 설명입니다.
- ③ 양쪽 끝에서 모두 넣고 뺄 수 있다.: 데크(Deque)의 설명입니다.
- ④ 운영체제의 작업 스케줄링에 주로 쓰인다.: 큐의 쓰임새입니다.
문제 3. 뿌리(루트)가 A 이고, A 의 왼쪽 자식이 B, 오른쪽 자식이 C 이며, B 의 왼쪽 자식이 D, 오른쪽 자식이 E 인 이진 트리를 전위(Preorder) 순회한 결과는?
- ① A B D E C
- ② D B E A C
- ③ D E B C A
- ④ A B C D E
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ① A B D E C
핵심: 전위 순회: 뿌리 → 왼쪽 → 오른쪽
- 뿌리 A 를 방문
- 왼쪽 서브트리(B)로: B 방문 → B 의 왼쪽 D → B 의 오른쪽 E
- 오른쪽 서브트리 C 방문
- 결과: A B D E C
틀린 선지
- ② D B E A C: 중위 순회(왼쪽 → 뿌리 → 오른쪽)의 결과입니다.
- ③ D E B C A: 후위 순회(왼쪽 → 오른쪽 → 뿌리)의 결과입니다.
- ④ A B C D E: 위에서부터 한 층씩 읽은 레벨 순회의 결과입니다.