정보처리기사 자료구조와 알고리즘 핵심정리
2026년 출제기준 반영
자료구조와 알고리즘, 핵심정리
- 스택은 나중에 넣은 것이 먼저 나오고(LIFO), 큐는 먼저 넣은 것이 먼저 나옵니다(FIFO).
- 트리 순회: 전위(뿌리 → 왼쪽 → 오른쪽), 중위(왼쪽 → 뿌리 → 오른쪽), 후위(왼쪽 → 오른쪽 → 뿌리).
- 버블·선택·삽입 정렬은 평균 O(n²), 퀵·병합·힙 정렬은 평균 O(n log n)입니다.
- 이진 검색은 정렬된 자료에서만 쓸 수 있고 시간 복잡도는 O(log n)입니다.
- 중요도
- ★★★★★ (5 / 5)
- 출제 비중
- 소프트웨어 개발 20문항 중 약 8문항 (40%)
스택·큐·트리 같은 자료구조, 트리 순회, 정렬과 검색 알고리즘을 다룹니다.
📖 자료구조와 알고리즘 개념 정리 더보기 →자료구조와 알고리즘 대표 문제 10개
문제 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: 위에서부터 한 층씩 읽은 레벨 순회의 결과입니다.
문제 4. 이진 탐색(Binary Search)을 쓰기 위한 전제 조건은?
- ① 자료가 정렬되어 있어야 한다
- ② 자료의 개수가 짝수여야 한다
- ③ 자료가 연결 리스트에 들어 있어야 한다
- ④ 같은 값의 자료가 없어야 한다
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ① 자료가 정렬되어 있어야 한다
핵심: 이진 탐색: 정렬된 자료, 시간 복잡도 O(log n)
이진 탐색은 가운데 값과 비교해 찾는 범위를 절반씩 줄여 갑니다. 크고 작음으로 절반을 버리려면 자료가 정렬되어 있어야 합니다.
틀린 선지
- ② 자료의 개수가 짝수여야 한다: 개수가 홀수든 짝수든 쓸 수 있습니다.
- ③ 자료가 연결 리스트에 들어 있어야 한다: 가운데 자료를 바로 찾아가야 하므로 배열이 알맞습니다.
- ④ 같은 값의 자료가 없어야 한다: 같은 값이 있어도 탐색할 수 있습니다.
문제 5. 자료 [5, 3, 8, 1] 을 버블 정렬로 오름차순 정렬할 때, 1회전(Pass 1)이 끝난 뒤의 결과는?
- ① [3, 5, 8, 1]
- ② [1, 3, 5, 8]
- ③ [3, 5, 1, 8]
- ④ [1, 5, 3, 8]
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ③ [3, 5, 1, 8]
핵심: 버블 정렬: 이웃한 두 값을 비교해 큰 값을 뒤로 보낸다
이웃한 두 값을 앞에서부터 차례로 비교합니다.
- 5 와 3 비교 → 바꿈 → [3, 5, 8, 1]
- 5 와 8 비교 → 그대로 → [3, 5, 8, 1]
- 8 과 1 비교 → 바꿈 → [3, 5, 1, 8]
1회전이 끝나면 가장 큰 값(8)이 맨 뒤에 놓입니다.
틀린 선지
- ① [3, 5, 8, 1]: 첫 번째 비교만 한 결과입니다.
- ② [1, 3, 5, 8]: 정렬이 모두 끝난 결과입니다.
- ④ [1, 5, 3, 8]: 선택 정렬 1회전의 결과입니다.
문제 6. 뿌리(루트)가 A 이고, A 의 왼쪽 자식이 B, 오른쪽 자식이 C 이며, B 의 왼쪽 자식이 D, 오른쪽 자식이 E 인 이진 트리를 중위(Inorder) 순회한 결과는?
- ① A B C D E
- ② A B D E C
- ③ D B E A C
- ④ D E B C A
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ③ D B E A C
핵심: 중위 순회: 왼쪽 → 루트 → 오른쪽
- 중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서입니다.
- A 의 왼쪽(B 가 뿌리인 트리)을 먼저: D → B → E
- 루트 A
- 오른쪽 C
- 답: D B E A C
틀린 선지
- ① A B C D E: 위에서부터 층별로 방문하는 레벨 순회의 결과입니다.
- ② A B D E C: 루트를 먼저 방문하는 전위 순회의 결과입니다.
- ④ D E B C A: 루트를 마지막에 방문하는 후위 순회의 결과입니다.
문제 7. 자료 [5, 3, 8, 1] 을 선택 정렬로 오름차순 정렬할 때, 1회전이 끝난 뒤의 결과는?
- ① [3, 5, 8, 1]
- ② [1, 3, 8, 5]
- ③ [1, 3, 5, 8]
- ④ [3, 5, 1, 8]
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ② [1, 3, 8, 5]
핵심: 선택 정렬: 가장 작은 값을 찾아 맨 앞과 맞바꾼다
- 선택 정렬은 남은 자료 가운데 가장 작은 값을 찾습니다. → 1
- 그 값을 맨 앞의 값(5)과 맞바꿉니다.
- 결과: [1, 3, 8, 5]
틀린 선지
- ① [3, 5, 8, 1]: 삽입 정렬의 1회전 결과입니다.
- ③ [1, 3, 5, 8]: 정렬이 모두 끝난 뒤의 결과입니다.
- ④ [3, 5, 1, 8]: 이웃한 자료끼리 비교해 바꾸는 버블 정렬의 1회전 결과입니다.
문제 8. 정렬 알고리즘의 평균 시간 복잡도가 O(n log n)이 아닌 것은?
- ① 퀵 정렬
- ② 병합(합병) 정렬
- ③ 힙 정렬
- ④ 삽입 정렬
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ④ 삽입 정렬
핵심: 삽입·선택·버블 정렬은 O(n²), 퀵·병합·힙 정렬은 O(n log n)
삽입 정렬은 평균 O(n²)입니다. 자료가 이미 거의 정렬되어 있을 때만 O(n)으로 빨라집니다.
틀린 선지
- ① 퀵 정렬: 평균 O(n log n)입니다. 다만 최악의 경우에는 O(n²)입니다.
- ② 병합(합병) 정렬: 언제나 O(n log n)입니다.
- ③ 힙 정렬: 언제나 O(n log n)입니다.
문제 9. 후위 표기식 3 4 + 5 * 를 계산한 결과는?
- ① 17
- ② 23
- ③ 35
- ④ 60
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ③ 35
핵심: 후위 표기식은 스택으로 계산한다: 숫자는 넣고, 연산자가 나오면 두 개를 꺼내 계산
- 3 을 넣음 → [3]
- 4 를 넣음 → [3, 4]
- + 를 만남 → 3 + 4 = 7 → [7]
- 5 를 넣음 → [7, 5]
- * 를 만남 → 7 × 5 = 35
일반 식으로 바꾸면 (3 + 4) × 5 입니다.
틀린 선지
- ① 17: 3 × 4 + 5 로 계산한 값입니다.
- ② 23: 3 + 4 × 5 로 계산한 값입니다.
- ④ 60: 세 수를 모두 곱한 값입니다.
문제 10. 해싱 함수 가운데, 키를 여러 부분으로 나눈 뒤 각 부분의 값을 더하거나 XOR 한 값을 주소로 쓰는 방법은?
- ① 제산법
- ② 제곱법
- ③ 숫자 분석법
- ④ 폴딩법
▼ 정답과 해설 보기▲ 정답과 해설 접기
정답: ④ 폴딩법
핵심: 폴딩법: 키를 접듯이 나누어 더하거나 XOR
폴딩법(Folding)은 종이를 접듯 키를 여러 조각으로 나누어 합치는 방법입니다.
틀린 선지
- ① 제산법: 키를 어떤 수로 나눈 나머지를 주소로 쓰는 방법입니다.
- ② 제곱법: 키를 제곱한 값의 가운데 부분을 주소로 쓰는 방법입니다.
- ③ 숫자 분석법: 키의 숫자 분포를 살펴 고르게 나타나는 자리를 골라 주소로 쓰는 방법입니다.
직접 풀어서 확인해 보세요.
AI 작성 · 운영진 검수 전