컴퓨터시스템기사 필기 08 — 자료구조 활용 (스택·큐·트리·정렬·해싱)

컴퓨터시스템기사 필기 08 — 자료구조 활용 (스택·큐·트리·정렬·해싱)

3과목 [3-1] 자료구조 활용 파트입니다.
트리 순회, 정렬 시간복잡도, 해시 함수 종류는 매 회차 출제돼요.

---

선형 자료구조

스택 (Stack) ⭐⭐

LIFO (Last In First Out) — 나중에 들어간 것이 먼저 나옴

주요 연산:
  push — 데이터 삽입 (top 증가)
  pop  — 데이터 삭제 (top 감소)
  peek — top 데이터 확인 (삭제 없음)

활용: 함수 호출(복귀 주소), 후위표기법 연산, 괄호 검사

 

스택 push/pop 추론:

push 순서: A, B, C
pop 순서:  C, B, A

 

큐 (Queue) ⭐

FIFO (First In First Out) — 먼저 들어간 것이 먼저 나옴

주요 연산:
  enqueue — 뒤(rear)에 삽입
  dequeue — 앞(front)에서 삭제

활용: OS 스케줄링, 프린터 대기열, 네트워크 패킷 처리

⚠️ OS 스케줄링은 큐(FIFO), 스택(LIFO) 아님!

 

연결 리스트 (Linked List)

동적 크기 조절 가능
삽입·삭제 O(1) — 배열보다 유리
탐색 O(n) — 배열보다 불리 (랜덤 접근 불가)

 

기출 문제

Q. 스택의 특성을 활용하는 대표적인 예는?

A. 함수 호출 시 복귀 주소 저장, 후위표기법(역폴란드 표기법) 연산

 

Q. OS 프로세스 스케줄링(FCFS)에 적합한 자료구조는?

A. 큐(Queue) — FIFO 방식

---

비선형 자료구조 — 트리 ⭐⭐⭐

트리 용어

루트(Root)  — 최상위 노드
리프(Leaf)  — 자식이 없는 단말 노드
차수(Degree) — 노드의 자식 수
높이(Height) — 루트에서 가장 깊은 리프까지의 경로 수

 

이진 트리 순회 ⭐⭐⭐

전위 순회 (Preorder):  루트 → 왼쪽 → 오른쪽
중위 순회 (Inorder):   왼쪽 → 루트 → 오른쪽
후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트

 

예시 트리:

        A
       / \
      B   C
     / \
    D   E

전위: A → B → D → E → C
중위: D → B → E → A → C
후위: D → E → B → C → A

 

이진 탐색 트리 (BST)

왼쪽 자식 < 부모 < 오른쪽 자식

탐색: O(log n) 평균, O(n) 최악 (편향 트리)
중위 순회하면 오름차순 정렬된 결과

 

기출 문제

Q. 다음 트리를 후위 순회한 결과는?

    A
   / \
  B   C
 /
D

A. D → B → C → A (왼→오→루트 반복)

---

정렬 알고리즘 ⭐⭐⭐

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	특징
버블 정렬	O(n²)	O(n²)	O(1)	안정, 단순
선택 정렬	O(n²)	O(n²)	O(1)	불안정, 단순
삽입 정렬	O(n²)	O(n²)	O(1)	안정, 거의 정렬된 경우 빠름
퀵 정렬	O(n log n)	O(n²)	O(log n)	불안정, 실용적으로 가장 빠름
합병 정렬	O(n log n)	O(n log n)	O(n)	안정, 안정적 성능
힙 정렬	O(n log n)	O(n log n)	O(1)	불안정

O(n²): 버블, 선택, 삽입
O(n log n): 퀵, 합병, 힙

 

기출 문제

Q. 다음 중 평균 시간복잡도가 O(n log n)인 정렬 알고리즘은?

A. 퀵 정렬, 합병 정렬, 힙 정렬

 

Q. 최악의 경우 시간복잡도가 O(n²)인 정렬 중 실용적으로 가장 빠른 것은?

A. 퀵 정렬 — 최악은 O(n²)이지만 평균 O(n log n)으로 실용적으로 가장 빠름

---

탐색 알고리즘 ⭐

순차 탐색 (Linear Search)
  → 처음부터 끝까지 순서대로 탐색
  → O(n)

이진 탐색 (Binary Search)
  → 정렬된 데이터에서 중간값과 비교해 반씩 줄임
  → O(log n)
  → ⚠️ 반드시 정렬되어 있어야 함!

---

해시 (Hash) ⭐⭐

해시 함수 종류

제산법 (Division Method)
  → 키를 특정 수로 나눈 나머지를 주소로 사용
  → h(k) = k mod m

폴딩법 (Folding Method)
  → 키를 여러 부분으로 나눠 더한 값을 주소로 사용

자릿수 분석법 (Digit Analysis)
  → 키의 각 자릿수 분포를 분석해 주소 결정

제곱법 (Mid-Square Method)
  → 키를 제곱한 후 중간 비트를 주소로 사용

⚠️ "최소제곱법"은 해시 함수에 속하지 않음!

 

충돌 해결 방법

개방 주소법 (Open Addressing)
  선형 탐사 — 다음 빈 자리 순차 탐색
  이차 탐사 — 거리를 제곱수로 늘려 탐색

체이닝 (Chaining)
  → 충돌 발생 시 연결 리스트로 연결

 

기출 문제

Q. 해시 함수의 종류가 아닌 것은?

A. 최소제곱법 — 제산법, 폴딩법, 자릿수분석법, 제곱법이 해시 함수

---

그래프 ⭐

정점(Vertex) + 간선(Edge)으로 구성

방향 그래프 — 간선에 방향 있음
무방향 그래프 — 방향 없음

탐색 방법:
  DFS (깊이 우선 탐색) — 스택 또는 재귀
  BFS (너비 우선 탐색) — 큐 사용

---

💡 실무에서는?

인프라 아키텍트로 네트워크 경로 최적화(최단 경로 알고리즘, 다익스트라), 보안 이벤트 처리 큐(SIEM에서 이벤트 수신 시 큐에 쌓고 순서대로 분석), 방화벽 규칙 트리 탐색 등에서 자료구조가 직접 쓰여요. 특히 IP 주소 매핑에 트리(트라이) 구조를 쓰는 게 라우터의 핵심 원리예요.

---

핵심 정리

✅ 스택=LIFO(함수호출) / 큐=FIFO(OS스케줄링)
✅ 전위=루트→좌→우 / 중위=좌→루트→우 / 후위=좌→우→루트
✅ O(n²): 버블/선택/삽입
✅ O(nlogn): 퀵/합병/힙
✅ 퀵 최악=O(n²)이지만 평균 가장 빠름
✅ 이진탐색=반드시 정렬 필요, O(logn)
✅ 해시함수: 제산법/폴딩법/자릿수분석/제곱법
✅ "최소제곱법"은 해시함수 아님!

 

다음 편에서는 프로그래밍 언어 활용 — C언어·객체지향·BNF으로 이어갑니다!

 

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

 

2026.08.12 - [자격증 정복/컴퓨터시스템기사] - 컴퓨터시스템기사 필기 07 — 컴퓨터 구조 응용 (병렬처리·Flynn분류·클라우드컴퓨팅)

컴퓨터시스템기사 필기 07 — 컴퓨터 구조 응용 (병렬처리·Flynn분류·클라우드컴퓨팅)

2026.08.11 - [자격증 정복/컴퓨터시스템기사] - 컴퓨터시스템기사 필기 06 — 컴퓨터 기억 및 입출력장치 (캐시·DMA·인터럽트·채널)

컴퓨터시스템기사 필기 06 — 컴퓨터 기억 및 입출력장치 (캐시·DMA·인터럽트·채널)