컴퓨터시스템기사 실기 02 — 자료구조 I (스택·큐·트리 순회·정렬·탐색)

컴퓨터시스템기사 실기 02 — 자료구조 I (스택·큐·트리 순회·정렬·탐색)

출제기준(실기) 4. 자료구조 활용 — 4-1 기본 자료구조 활용(연결 리스트·스택·큐·트리), 4-2 정렬 및 탐색
수식 표기법 변환과 트리 순회는 복원 기출에서 거의 매 회차 반복됩니다. 계산 과정까지 쓰는 연습이 핵심이에요!

01편에서 6개 주요항목 맵을 정리했으니, 이번 편부터 항목별로 들어갑니다.

자료구조는 2026년 개편 출제기준에서 독립 항목이 되었고, 구 기출에서도 표기법 변환과 트리 순회가 반복해서 나온 영역입니다.

---

이번 편의 출제기준 위치

코드	세세항목
4-1-1	연결 리스트를 활용할 수 있다
4-1-2	스택을 활용할 수 있다
4-1-3	큐를 활용할 수 있다
4-1-4	트리를 활용할 수 있다
4-2-1	주어진 자료를 정렬할 수 있다
4-2-2	주어진 자료를 탐색할 수 있다

---

실기 출제 포인트

복원 기출 정리 파일에서 확인한 출제 현황입니다.

유형	확인된 회차	중요도
수식 후위·전위 표기 변환	2017-3(전위), 2020 수시, 2020 통합, 2021-1, 2021-3, 2024-1(전위), 2024-3·2025-1·2025-3(2021-3과 동일 문항)	⭐⭐⭐
트리 순회 (후위·전위)	2018-1·2018-3(후위), B형 2019-11(전위)	⭐⭐⭐
트리의 차수·단말 노드	2016-1, 2020-3, 2025-1(동일 문항)	⭐⭐
재귀 호출의 지역 변수·복귀 주소 저장 구조 → 스택	2026-1 Q14	⭐⭐
0-주소 명령어 스택 PUSH/POP 추적	2020 통합, 2024-3	⭐⭐
정렬 C 코드 출력 예측	2021-1, 2022-1	⭐⭐
AVL 트리	2026-1 Q18 (원문 불완전 복원)	⭐⭐
비교 정렬 하한	2026-1 Q19	⭐⭐
연결 리스트·큐·이진 탐색 직접 출제	확인 안 됨 (출제기준에는 있으므로 개념 정리)	⭐

---

키워드 박스 (답안 필수 단어)

스택     — LIFO, push / pop, top, 오버플로 / 언더플로
큐       — FIFO, enqueue / dequeue, front / rear, 원형 큐
연결 리스트 — 노드(data + next), head, 삽입·삭제 O(1), 탐색 O(n)
트리     — 루트, 노드의 차수, 트리의 차수, 단말 노드, 높이
순회     — 전위(Root-Left-Right), 중위(Left-Root-Right), 후위(Left-Right-Root)
AVL      — 균형 인수 |왼쪽 높이 − 오른쪽 높이| ≤ 1, 회전 LL / RR / LR / RL
정렬     — 비교 정렬 하한 Ω(n log n), 안정성, 평균·최악 시간 복잡도
탐색     — 순차 O(n), 이진 O(log n) (정렬된 자료가 전제)

---

스택과 큐 ⭐⭐

구조	원리	대표 연산	시간 복잡도	대표 활용
구조	원리	대표 연산	시간 복잡도	대표 활용
스택	LIFO (나중에 들어간 것이 먼저 나옴)	push, pop	O(1)	함수 호출·복귀 주소, 후위 표기 계산, 괄호 검사, DFS
큐	FIFO (먼저 들어간 것이 먼저 나옴)	enqueue, dequeue	O(1) (원형 큐)	준비 큐(스케줄링), 버퍼, BFS
덱	양쪽 끝에서 입출력	4가지 연산	O(1)	스택·큐 겸용

스택 오류:  오버플로(가득 찬 스택에 push) / 언더플로(빈 스택에서 pop)
큐 오류:    가득 찬 큐에 enqueue / 빈 큐에서 dequeue
원형 큐:    rear가 끝에 닿으면 앞으로 돌아와서 빈 칸을 재사용

---

수식 표기법 변환 ⭐⭐⭐

같은 수식을 연산자 위치에 따라 세 가지로 씁니다. A + B * C로 비교해 보세요.

표기법	연산자 위치	결과
중위(Infix)	피연산자 사이	A + B * C
전위(Prefix)	피연산자 앞	+ A * B C
후위(Postfix)	피연산자 뒤	A B C * +

 

변환 방법

후위 변환 (괄호 → 우선순위 → 같은 우선순위는 왼쪽부터)
  1. 괄호 안을 먼저 변환
  2. 우선순위가 높은 연산자부터 "피연산자 피연산자 연산자"로 묶음
  3. 우선순위가 같으면 왼쪽 연산이 먼저 (좌결합)

예) A / B * ( C - D ) + E
  ( C - D )          → C D -
  A / B              → A B /
  ( A B / ) * ( C D - ) → A B / C D - *
  ( A B / C D - * ) + E → A B / C D - * E +

전위 변환: 같은 방식으로 묶되 연산자를 맨 앞에 둔다
예) A / B * ( C + D ) + E
  ( C + D )   → + C D
  A / B       → / A B
  ( / A B ) * ( + C D ) → * / A B + C D
  ( * / A B + C D ) + E → + * / A B + C D E

 

 

⚠️ 함정 패턴

"/ 와 * 는 우선순위가 같다 → 오른쪽의 (C-D)부터 묶는다" → 오답! (같으면 왼쪽부터)
"대입문 X = ... 을 변환할 때 = 를 빼먹음" → 감점! (후위에서는 X 우변결과 = 순서)
"전위와 후위를 헷갈려 연산자를 반대쪽에 둠" → 오답!

 

기출 모음

문제	정답	출제
A / B * (C − D) + E → 후위	A B / C D − * E +	2020 통합, 2021-1
A / B * (C + D) + E → 전위	+ * / A B + C D E	2024-1
A * B + C → 전위	+ * A B C	2017-3
X = A + B + C / D * E − F → 후위	X A B + C D / E * + F − =	2021-3, 2024-3, 2025-1, 2025-3
A / (B × C) − D + E / F → 후위	A B C * / D − E F / +	2020 수시 (원문에 정답 없음, 직접 계산)

후위식 값 계산 (스택 사용)

후위식은 왼쪽부터 읽으면서 피연산자는 push, 연산자는 pop 2번 후 계산 결과를 push 합니다.

식:  8 2 / 5 3 - * 1 +

push 8, push 2   → [8, 2]
  /              → 8 / 2 = 4        → [4]
push 5, push 3   → [4, 5, 3]
  -              → 5 - 3 = 2        → [4, 2]
  *              → 4 * 2 = 8        → [8]
push 1           → [8, 1]
  +              → 8 + 1 = 9        → [9]

결과: 9

0-주소 명령어의 스택 추적 (2020 통합, 2024-3)

0-주소 명령어는 피연산자를 스택에서 꺼내 씁니다. 같은 후위 표기 원리입니다.

A = B * ( C + D * E - F / G )

PUSH B → [B]
PUSH C → [B, C]
PUSH D → [B, C, D]
PUSH E → [B, C, D, E]
(1) MUL → D*E          → [B, C, (D*E)]
(2) ADD → C + D*E      → [B, (C+D*E)]
PUSH F → [B, (C+D*E), F]
PUSH G → [B, (C+D*E), F, G]
(3) DIV → F/G          → [B, (C+D*E), (F/G)]
(4) SUB → C+D*E − F/G  → [B, (C+D*E−F/G)]
(5) MUL → B * (...)    → [B*(C+D*E−F/G)]
POP A  → 결과를 A에 저장

 

기출 정답은 (1) MUL, (2) ADD, (3) DIV, (4) SUB, (5) MUL 순서입니다.

04편(프로세서와 명령어)에서 명령어 관점으로 다시 다룹니다.

---

연결 리스트 ⭐

구분	배열	연결 리스트
접근	인덱스로 O(1)	처음부터 따라가야 해서 O(n)
삽입·삭제	뒤의 요소를 밀어야 해서 O(n)	위치를 알면 포인터만 바꿔 O(1)
메모리	연속 공간	노드마다 포인터 공간이 추가로 필요

단순 연결 리스트: next 포인터만 있음 (한 방향)
이중 연결 리스트: prev + next (양방향)
원형 연결 리스트: 마지막 노드가 첫 노드를 가리킴

struct Node { int data; struct Node *next; };

/* head 앞에 새 노드 삽입 */
new_node->next = head;   /* 1) 새 노드가 기존 head를 가리키게 한 뒤 */
head = new_node;         /* 2) head를 새 노드로 바꾼다 */

/* p 다음 노드 삭제 */
tmp = p->next;
p->next = tmp->next;     /* tmp를 건너뛰도록 연결 */

 

⚠️ 삽입 순서를 바꿔 head = new_node를 먼저 하면 기존 리스트를 가리키던 포인터를 잃어서 리스트가 끊깁니다.

---

트리 ⭐⭐⭐

용어와 차수 계산 (2016-1, 2020-3, 2025-1)

              A
          /   |   \
         B    C    D
        / \   |   / \
       E   F  G  H   I
      / \       / | \
     J   K     L  M  N

노드의 차수  = 그 노드의 자식 수
트리의 차수  = 노드의 차수 중 최댓값
단말 노드   = 차수가 0인 노드 (자식이 없는 노드)

A=3  B=2  C=1  D=2  E=2  H=3  (나머지는 0)
→ 트리의 차수 = 3
→ 단말 노드 = J, K, F, G, L, M, N, I

 

트리 순회 3종 ⭐⭐⭐

전위(Preorder)  : Root → Left → Right    (루트가 앞)
중위(Inorder)   : Left → Root → Right    (루트가 가운데)
후위(Postorder) : Left → Right → Root    (루트가 뒤)

 

기출 후위 순회 문제(2018-1, 2018-3, 2015-10 유사)의 트리입니다. 그림은 해설을 바탕으로 다시 그렸습니다.

            A
           / \
          B   C
         /   / \
        D   E   F
           / \
          G   H

전위:  A B D C E G H F
중위:  D B A G E H C F
후위:  D B G H E F C A   ← 기출 정답

후위 풀이:
  1) 왼쪽 서브트리 B → D, B
  2) 오른쪽 서브트리 C → (E의 왼쪽 G, 오른쪽 H, 루트 E), F, C
  3) 마지막에 루트 A
  → D B G H E F C A

 

 

⚠️ 함정 패턴

"후위 순회는 루트를 먼저 방문한다" → 오답! (루트는 맨 마지막)
"서브트리 안에서는 순서가 자유롭다" → 오답! (각 서브트리에도 같은 규칙을 재귀 적용)
"B형 2019-11처럼 그림이 크면 한 번에 풀려고 함" → 서브트리 단위로 쪼개서 풀기

 

AVL 트리 ⭐⭐

정의:  모든 노드에서 |왼쪽 서브트리 높이 − 오른쪽 서브트리 높이| ≤ 1
       (균형 인수가 −1, 0, 1)
복구:  삽입·삭제 후 불균형이 생기면 회전으로 균형을 맞춤
성능:  검색·삽입·삭제 모두 O(log n)

불균형 유형	회전 방법
LL (왼쪽-왼쪽)	오른쪽 회전 1회
RR (오른쪽-오른쪽)	왼쪽 회전 1회
LR (왼쪽-오른쪽)	왼쪽 자식을 왼쪽 회전한 뒤, 노드를 오른쪽 회전
RL (오른쪽-왼쪽)	오른쪽 자식을 오른쪽 회전한 뒤, 노드를 왼쪽 회전

 

⚠️ 2026년 1회 Q18은 원문이 불완전하게 복원되어 있고, "서브트리 높이 차이 1 이하 → AVL 트리"라는 키워드만 확인됩니다.

높이 차 조건이 나오면 AVL이라고 답하세요.

---

정렬 ⭐⭐

알고리즘	최선	평균	최악	공간	안정성
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	불안정
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	안정
버블 정렬	O(n) (교환 없으면 종료하는 개선형)	O(n²)	O(n²)	O(1)	안정
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	안정
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)	불안정
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	불안정

 

비교 정렬의 하한 (2026-1 Q19)

비교 기반 정렬은 어떤 알고리즘이든 최악의 경우 Ω(n log n) 이하로 줄일 수 없다

이유:  n개를 정렬한 결과는 n!가지 순열 중 하나
       비교 결과(예/아니오)로 구분하는 결정 트리의 잎이 최소 n!개
       트리 높이 ≥ log2(n!) ≈ n log n
→ 기출 답: O(n log n)

 

⚠️ 이 하한은 비교 기반 정렬에만 적용됩니다. 비교를 하지 않는 정렬(계수 정렬 등)에는 해당하지 않아요.

 

정렬 C 코드 출력 예측 (2021-1, 2022-1)

for (a = 0; a < len; a++)
    for (b = 0; b < len - 1 - a; b++)
        if (ct[b] > ct[b + 1]) {   /* 인접 요소 비교 후 교환 (버블 정렬) */
            tmp = ct[b]; ct[b] = ct[b + 1]; ct[b + 1] = tmp;
        }

2022-1 (정답 41234): ct = {4, 2, 1, 3}, len = 4
  sort 함수 첫 줄에서 len을 출력 → 4
  a=0: {4,2,1,3} → {2,4,1,3} → {2,1,4,3} → {2,1,3,4}
  a=1: {2,1,3,4} → {1,2,3,4}
  이후 교환 없음
  main에서 ct[0]~ct[3] 출력 → 1234
  → 4 + 1234 = 41234
  (기출은 내부 반복 조건이 b < 3 - a로 고정되어 있었음)

2021-1 (정답 9580705035): ct = {95, 50, 80, 35, 70}을 내림차순 정렬
  → {95, 80, 70, 50, 35}
  printf("%d")에 구분 문자가 없으므로 붙여서 출력
  → 9580705035

 

⚠️ 출력 예측에서는 printf 서식에 공백·줄바꿈이 있는지 반드시 확인하세요. 구분이 없으면 숫자가 붙어서 나옵니다.

---

탐색 ⭐

방법	시간 복잡도	조건
순차 탐색	O(n)	정렬 여부와 무관
이진 탐색	O(log n)	정렬된 자료가 전제

이진 탐색 예) [3, 8, 12, 19, 25, 31, 40] 에서 25 찾기
  low=0, high=6 → mid=3 (19)   25 > 19 → low=4
  low=4, high=6 → mid=5 (31)   25 < 31 → high=4
  low=4, high=4 → mid=4 (25)   찾음
→ 비교 3회

---

기출 Q&A

Q. Infix 수식 A / B * (C − D) + E를 Postfix로 변환하시오.

A. A B / C D − * E +
(2020 통합, 2021-1 동일 문항) 괄호 안 → 왼쪽부터 / 와 * → 마지막 +

 

Q. 다음 트리를 후위 순회한 결과를 쓰시오. (2018-1, 2018-3 트리: A 루트, B(D), C(E(G, H), F))

A. D B G H E F C A
왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서를 각 서브트리마다 적용

 

Q. 위의 차수 계산 트리(A~N)의 차수와 단말 노드는?

A. 트리의 차수 3, 단말 노드 J, K, F, G, L, M, N, I
(2016-1, 2020-3, 2025-1 동일 문항) 노드 A와 H의 차수 3이 최댓값

 

Q. 재귀 호출에서 지역 변수와 돌아올 복귀 주소를 저장하는 자료구조는?

A. 스택(Stack)
(2026-1 Q14) 함수가 호출될 때마다 스택 프레임이 쌓이고, 리턴하면 LIFO 순서로 하나씩 꺼내며 복귀합니다.

 

Q. 비교 기반 정렬의 최악 시간 복잡도 하한을 쓰시오.

A. O(n log n)
(2026-1) 결정 트리의 잎이 n!개 이상이므로 높이는 log2(n!) ≈ n log n

---

예상 문제 (직접 만든 문제)

Q1. 전위 순회 결과가 A B D E C, 중위 순회 결과가 D B E A C일 때 후위 순회 결과는?

A1. D E B C A
전위의 첫 값 A가 루트 → 중위에서 A 왼쪽(D B E)이 왼쪽 서브트리, 오른쪽(C)이 오른쪽 서브트리 → B가 왼쪽 서브트리의 루트(D 왼쪽, E 오른쪽)

 

Q2. 후위식 8 2 / 5 3 - * 1 +의 값은?

A2. 9 (위 스택 계산 과정 참고)

 

Q3. 정렬된 배열 [3, 8, 12, 19, 25, 31, 40]에서 25를 이진 탐색할 때 비교 횟수는?

A3. 3회 (mid 값 19 → 31 → 25)

---

💡 실무에서는?

• 스택: 함수 호출 시 복귀 주소가 스택에 쌓이기 때문에, 재귀가 너무 깊어지면 스택 오버플로로 프로세스가 죽습니다. 보안 점검에서 버퍼 오버플로가 복귀 주소를 덮어쓰는 공격을 설명할 때도 같은 구조를 씁니다.
• 큐: 메시지 큐나 로그 수집 파이프라인에서 생산자와 소비자 속도 차이를 흡수하는 버퍼 역할을 합니다.
• 트리: 디렉터리 구조가 트리입니다. tree나 find는 디렉터리를 순회하고, rm -r은 자식을 먼저 지우고 부모를 지우는 후위 순회 방식입니다.
• 정렬·탐색: 로그 분석에서 sort로 정렬한 파일은 이진 탐색으로 빠르게 찾을 수 있고, 정렬 안 된 로그는 순차로 훑어야 해서 크기가 커질수록 느려집니다.

---

핵심 정리

✅ 스택=LIFO(push/pop) / 큐=FIFO(enqueue/dequeue)
✅ 후위 변환: 괄호 → 우선순위 → 같으면 왼쪽부터, 전위는 연산자를 앞에
✅ 후위식 계산: 피연산자 push, 연산자는 pop 2번 후 결과 push
✅ 트리의 차수 = 노드 차수의 최댓값 / 단말 노드 = 차수 0
✅ 전위 NLR / 중위 LNR / 후위 LRN — 서브트리마다 재귀 적용
✅ AVL = 높이 차 1 이하, 회전 LL·RR·LR·RL
✅ 비교 정렬 하한 Ω(n log n) / 퀵 정렬 최악 O(n²)
✅ 이진 탐색은 정렬된 자료만 가능, O(log n)
✅ C 출력 예측은 printf 서식(구분 문자 유무) 확인

 

다음 편에서는 자료구조 II (그래프·인덱스·해싱)로 이어갑니다!

 

궁금한 점은 댓글로 남겨주세요!