자료구조 중간고사 총정리 & 예상문제 풀이

📌 과목 개요

• 과목명: 자료구조
• 교재: 『파이썬으로 쉽게 배우는 자료구조 (개정판)』 - 최영규, 천인국
• 시험 범위: Chapter 1 ~ Chapter 3
• 시험 스타일: 구현 코드, 시간복잡도, 출력 결과 예측, 개념 설명

---

📚 핵심 요약 (Chapter 1 ~ 3)

🔹 Chapter 1 - 개념과 시간복잡도

• 자료구조 = 데이터를 효율적으로 표현하는 방식
• 추상 자료형(ADT) = 기능만 제공하고 구현은 숨긴 구조
• 시간복잡도 = 알고리즘 성능 측정 기준, 최악(Worst Case) 기준으로 생각!

🔹 Chapter 2 - 리스트

• 배열 기반 리스트: 접근 빠름(O(1)), 삽입/삭제 느림(O(n))
• 연결 리스트: 삽입/삭제 빠름(O(1)), 접근 느림(O(n))
• head, next, prev 포인터 흐름을 그리면서 이해!

🔹 Chapter 3 - 스택 & 큐

• 스택: 후입선출(LIFO), push, pop
• 큐: 선입선출(FIFO), enqueue, dequeue
• 파이썬의 pop(0)은 O(n), append()는 O(1)

---

🧪 자주 나오는 실전 문제 유형

✅ 1. 시간복잡도 예측

for i in range(n):
    for j in range(n):
        print(i, j)

✔️ 답: O(n²)

---

✅ 2. 연결 리스트 흐름 파악

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(1)
b = Node(2)
a.next = b
print(a.next.data)

✔️ 출력: 2

---

✅ 3. 스택 연산 흐름

s = Stack()
s.push(1)
s.push(2)
s.pop()
s.push(3)
print(s)

✔️ 출력: [1, 3]

---

✅ 4. 큐 연산 흐름

q = Queue()
q.enqueue('A')
q.enqueue('B')
q.dequeue()
q.enqueue('C')
print(q)

✔️ 출력: ['B', 'C']

---

✅ 5. ADT 개념 설명 (서술형 예시)

Q. 추상 자료형(ADT)이란 무엇인가요?
✔️ 답안 예시:

추상 자료형은 자료 구조의 논리적 정의와 연산의 집합을 의미하며,
내부 구현을 감추고 사용자에게 필요한 기능만 제공하는 구조입니다.

---

📌 시험 직전 체크리스트

☑ 시간복잡도 계산법 (이중 반복문, 재귀 등)
☑ 연결 리스트에서 포인터 흐름 (head, next)
☑ 스택/큐 출력 순서 흐름
☑ __str__() 호출 시 어떤 형태로 출력되는지
☑ 클래스 기반 코드에서 self.items의 변화 추적

---

📎 마무리 요약

• 시험에서는 "코드를 보고 출력/시간복잡도 예측" 문제가 자주 출제됨
• 기능만 제공하고 구현을 감추는 것 → ADT의 핵심
• 직접 손으로 써보고 시뮬레이션하면 실수 확률이 확 줄어듬!

---

✨ 응원 한 마디

자료구조는 개발 실력의 기초 체력!
시험공부는 끝났지만, 이 글은 다음 학기에도 분명히 다시 보게 될 보물창고가 될 거예요 💪