🧠 자료구조 기말 총정리 | 파이썬 코드와 함께 이해하는 구조의 세계

안녕하세요!
이번 포스트는 자료구조 기말고사 범위를 핵심 중심으로 정리한 총정리 노트입니다.
특히 교수님께서 강조하신 코드 해석, 시간 복잡도, __str__ 출력 포맷까지 모두 포함했어요!

---

✅ 1. 연결 리스트 (Linked List)

📌 개념 요약

• 노드(Node): 데이터 + 링크로 구성
• 단순 연결 리스트: 한 방향
• 이중 연결 리스트: 양방향
• 원형 리스트: 끝에서 다시 처음으로 연결

📌 코드 예시 (단순 연결 리스트)

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add_front(self, elem):
        self.head = Node(elem, self.head)

    def __str__(self):
        result = []
        node = self.head
        while node:
            result.append(str(node.data))
            node = node.next
        return " -> ".join(result)

✅ 시험 포인트

• __str__ 출력 결과 예측
• 삽입/삭제 알고리즘 → 시간 복잡도 O(1) or O(n)

---

✅ 2. 스택 (Stack)

📌 개념 요약

• LIFO (후입선출) 구조
• 연산: push, pop, peek, is_empty

📌 구현 예시 (리스트 기반)

class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def __str__(self):
        return str(self.data[::-1])  # top이 앞에 오도록 출력

✅ 시험 포인트

• 괄호 검사 알고리즘
• 미로 탈출(DFS 응용)
• 스택 구현 방식 비교: 리스트 vs 연결 리스트

---

✅ 3. 큐 (Queue)

📌 개념 요약

• FIFO (선입선출) 구조
• 연산: enqueue, dequeue, peek

📌 원형 큐 구현

class CircularQueue:
    def __init__(self, size=5):
        self.data = [None]*size
        self.front = 0
        self.rear = 0

    def is_full(self):
        return (self.rear+1) % len(self.data) == self.front

    def is_empty(self):
        return self.front == self.rear

    def enqueue(self, item):
        if not self.is_full():
            self.rear = (self.rear+1) % len(self.data)
            self.data[self.rear] = item

    def dequeue(self):
        if not self.is_empty():
            self.front = (self.front+1) % len(self.data)
            return self.data[self.front]

✅ 시험 포인트

• front, rear 이동 시 인덱스 계산
• 출력 결과 예상 문제
• 원형 큐의 특징: 공백 하나를 비워두는 이유

---

✅ 4. 덱 (Deque)

📌 개념 요약

• Double Ended Queue: 앞뒤에서 삽입/삭제 가능
• 연산: add_front, add_rear, delete_front, delete_rear

📌 시험 포인트

• 원형 덱 구조
• 삽입/삭제 시 front/rear 변화 추적

---

✅ 5. 트리 (Tree)

📌 개념 요약

• 계층적 자료구조 (부모-자식 관계)
• 용어: 루트, 단말노드, 서브트리, 깊이, 레벨 등
• 이진트리: 노드 당 최대 두 개의 자식

📌 순회 방법

순회 방식	방문 순서
전위	루트 → 왼쪽 → 오른쪽
중위	왼쪽 → 루트 → 오른쪽
후위	왼쪽 → 오른쪽 → 루트

 

📌 시험 포인트

• 순회 순서 → 출력 예상 문제
• 재귀 구현 코드 해석
• 이진탐색트리의 삽입/탐색 시간복잡도 O(log n)

---

✅ 6. 정렬 알고리즘

알고리즘	시간 복잡도	특징
선택 정렬	O(n²)	가장 작은/큰 값을 찾아 앞으로 이동
버블 정렬	O(n²)	인접한 값을 교환
삽입 정렬	O(n²)	앞쪽을 정렬된 상태로 유지하며 삽입
퀵 정렬	평균 O(n log n)	피벗 기준 분할 정복
병합 정렬	O(n log n)	안정 정렬, 분할과 병합

 

✅ 시험 포인트

• 코드 주고 결과/과정 예상
• 정렬 알고리즘 별 특징, 안정성, 복잡도 비교

---

🧠 시험 직전 핵심 암기 요약

• __str__ 결과 예상 → 연결 리스트, 큐, 트리 순회 등
• 시간 복잡도 → 리스트 기반 vs 연결 구조, 정렬 비교
• 순회 순서 → 트리 전/중/후위 구분
• 덱과 원형 큐 → front/rear 변화 따라가기
• 구현 코드 → 직접 해보며 흐름 익히기

---

📘 마무리

자료구조는 단순히 코드를 외우기보다 "어떻게 동작하는가"를 흐름으로 이해하는 게 핵심이에요.
직접 코드를 타이핑해보고, 출력값을 예측하면서 연습해보세요!