임베디드기사 필기 12 — 임베디드 소프트웨어 ① 데이터구조(스택·큐·트리순회·정렬·그래프)

임베디드기사 필기 12 — 임베디드 소프트웨어 ① 데이터구조(스택·큐·트리순회·정렬·그래프)

4과목 [4-1] 데이터 구조 파트입니다.
트리 차수, 후위 순회, 스택 LIFO vs 큐 FIFO 구분은 매 회차 출제돼요.

---

알고리즘 복잡도 ⭐

O(빅오)   — 최악의 경우 (가장 많이 쓰임)
Ω(오메가) — 최선의 경우
θ(세타)   — 평균적인 경우

 

정렬·탐색 복잡도:

O(n²):     버블, 삽입, 선택 정렬
O(n logn): 퀵(평균), 힙, 합병(2원) 정렬
O(n):      순차 탐색
O(logn):   이진 탐색 (정렬된 배열에서만 가능!)

---

배열 vs 연결 리스트 ⭐

배열:     임의 접근 가능 (빠른 읽기)
          삽입·삭제 느림 (밀거나 당겨야)

연결 리스트: 순차 접근만 가능
             삽입·삭제 빠름 (포인터만 변경)

 

원형 연결 리스트 ⭐:

마지막 노드가 첫 노드를 가리킴
⚠️ 원형 연결 리스트에는 널 포인터가 없음!
   (단순/이중/다중 연결 리스트는 끝에 NULL 있음)

 

기출 문제

Q. 널 포인터(null pointer)가 존재하지 않는 자료구조는?

A. 원형 연결 리스트 (순환 구조라 끝이 없음)

---

스택 (Stack) ⭐⭐⭐

LIFO (Last In First Out) — 후입선출

연산:
  PUSH — 삽입 (TOP 증가)
  POP  — 삭제 (TOP 감소)

활용:
  인터럽트 처리 (복귀 주소 저장)
  함수 호출 (복귀 주소·지역변수·매개변수)
  후위 표기법(Postfix) 연산

⚠️ "스택은 FIFO 방식이다" → 오답! (스택은 LIFO)

 

중위(Infix) → 후위(Postfix) 변환:

A + B * C / D

우선순위: *와 / 가 + 보다 높음
→ A + ((B*C)/D)
→ 후위: A B C * D / +

 

기출 문제

Q. 스택에서 C 함수의 지역변수와 호출 후 복귀 주소를 저장하는 메모리 처리 방식은?

A. 스택

---

큐 (Queue) ⭐⭐

FIFO (First In First Out) — 선입선출

연산:
  ENQUEUE — 뒤(Rear)에 삽입
  DEQUEUE — 앞(Front)에서 삭제

활용: OS 스케줄링, 프린터 대기열

데크(Deque): 양쪽 끝 모두 삽입·삭제 가능
              스택과 큐 동작 모두 가능

 

선형 vs 비선형 구조 ⭐:

선형 구조: 스택, 큐, 데크, 리스트, 배열
비선형 구조: 트리, 그래프

⚠️ "그래프는 선형 구조" → 오답!

 

기출 문제

Q. 선형 구조에 해당하는 자료구조를 모두 고르면?

A. 스택, 큐, 데크 (트리·그래프는 비선형)

---

트리 (Tree) ⭐⭐⭐

트리 용어

루트(Root)  — 최상위, 부모 없음
단말(Leaf)  — 자식 없음, 트리의 끝
차수(Degree) — 노드의 자식 수
트리의 차수 — 노드들의 차수 중 가장 큰 값 ⭐
간선 수     — n개 노드 → n-1개 간선

 

이진 트리

모든 노드의 차수 ≤ 2
레벨 k의 최대 노드 수 = 2^(k-1)
단말 노드 수(n₀) = 차수 2인 노드 수(n₂) + 1

 

트리 순회 ⭐⭐⭐ (최빈출!)

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

 

7개 노드 트리 예시 (반복 출제!):

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

후위 순회: C → D → B → F → G → E → A
전위 순회: A → B → C → D → E → F → G
중위 순회: C → B → D → A → F → E → G

 

기출 문제

Q. 트리의 차수(Degree of Tree)란?

A. 트리를 구성하는 노드들의 차수 중 가장 큰 값

 

Q. 7개 노드 트리(루트A, A의자식B·E, B의자식C·D, E의자식F·G)의 후위 순회 결과는?

A. C → D → B → F → G → E → A

---

그래프 ⭐

정점(Vertex) + 간선(Edge)

방향 그래프: 최대 간선 수 = n(n-1)
무방향 그래프: 최대 간선 수 = n(n-1)/2

n개 정점 연결 최소 간선 수 = n-1 (트리 구조)

 

탐색 방법:

DFS (깊이 우선 탐색) — 스택/재귀
BFS (너비 우선 탐색) — 큐

 

인접 행렬:

n개 정점 → n×n 행렬
간선 있으면 1, 없으면 0

 

기출 문제

Q. n개의 정점을 모두 연결하는 최소 간선 수는?

A. n-1개

---

문제 해결 기법

분할 정복 (Divide and Conquer) — 작은 문제로 나눠 풀고 합침
동적 계획법 (Dynamic Programming) — 부분 문제 결과 저장·재활용
탐욕법 (Greedy) — 매 순간 최선 선택
백트래킹 (Backtracking) — 가능성 없는 경로 가지치기

---

💡 실무에서는?

인프라 아키텍트로 네트워크 라우팅 최적화 알고리즘(다익스트라)이 그래프 BFS/DFS의 응용이에요.

방화벽 규칙 트리 탐색, SIEM 이벤트 처리 큐가 자료구조의 실제 활용 사례예요.

---

핵심 정리

✅ 스택=LIFO(후입선출) / 큐=FIFO(선입선출)
✅ "스택=FIFO" → 오답!
✅ 스택 활용: 인터럽트/함수복귀주소/후위표기법
✅ 선형: 스택/큐/데크/리스트 / 비선형: 트리/그래프
✅ 원형 연결 리스트 = 널 포인터 없음!
✅ 트리 차수 = 가장 큰 노드 차수
✅ n개 노드 → n-1개 간선
✅ 후위 순회: 좌→우→루트
✅ 7노드 후위: C→D→B→F→G→E→A
✅ O(n²): 버블/삽입/선택
✅ O(nlogn): 퀵/힙/합병
✅ 이진탐색: O(logn), 정렬된 배열에서만!

 

다음 편에서는 프로그래밍 — 포인터·구조체·OOP으로 이어갑니다!