Virtualization

자료구조 학습 계획

자료구조 학습 계획입니다. Big-O, list, stack, queue, linked list, hash table, tree, heap, graph 학습 순서와 실습 기록 방식을 정리했습니다.

devmes

• 조회 164

자료구조 학습 계획

자료구조와 알고리즘은 한 번에 외우는 과목이 아니라, 자료를 저장하는 방식과 연산 비용을 작은 코드로 반복 확인하는 학습에 가깝다. Python으로 시작하면 문법 부담을 줄이고 개념에 집중할 수 있다.

학습 순서

  1. 복잡도와 Big-O: 입력 크기와 실행 시간의 관계를 이해한다.
  2. Array/List: index 접근, append, insert, delete 비용을 비교한다.
  3. Stack, Queue, Deque: LIFO/FIFO와 collections.deque를 익힌다.
  4. Linked List: node, pointer, singly/doubly 구조를 구현한다.
  5. Hash Table: hash function, collision, chaining, open addressing을 정리한다.
  6. Tree: binary tree, traversal, binary search tree를 구현한다.
  7. Heap: priority queue와 heap sort를 연결해서 본다.
  8. Balanced Tree: AVL, Red-Black Tree는 개념과 회전 원리를 중심으로 본다.
  9. Graph: adjacency list/matrix, DFS, BFS, shortest path를 연습한다.

실습 디렉터리 구성

data-structure-study/
├── 01_big_o/
├── 02_list_stack_queue/
├── 03_linked_list/
├── 04_hash_table/
├── 05_tree_heap/
└── 06_graph/
mkdir -p data-structure-study/{01_big_o,02_list_stack_queue,03_linked_list,04_hash_table,05_tree_heap,06_graph}
cd data-structure-study

첫 주 목표

첫 주에는 복잡한 알고리즘보다 Python 기본 컨테이너의 비용을 체감하는 데 집중한다.

from collections import deque
from time import perf_counter


def measure(label: str, func) -> None:
    start = perf_counter()
    func()
    elapsed = perf_counter() - start
    print(f"{label}: {elapsed:.6f}s")


def list_pop_front():
    data = list(range(100_000))
    while data:
        data.pop(0)


def deque_pop_front():
    data = deque(range(100_000))
    while data:
        data.popleft()


measure("list pop(0)", list_pop_front)
measure("deque popleft", deque_pop_front)

기록 방식

각 주제마다 개념, 직접 구현, 표준 라이브러리 사용법, 시간복잡도, 실무 사용 예를 남긴다.

# Queue

## 개념
FIFO 구조. 먼저 들어온 작업을 먼저 처리한다.

## 직접 구현
...

## Python 표준 라이브러리
collections.deque

## 시간복잡도
append: O(1), popleft: O(1)

## 사용 예
작업 큐, BFS, 로그 처리 파이프라인

학습 기준

  • 그림만 보고 넘어가지 말고 최소 구현 코드를 작성한다.
  • 표준 라이브러리가 있는 구조는 직접 구현 후 표준 라이브러리와 비교한다.
  • Big-O를 말할 때는 어떤 연산 기준인지 함께 적는다.
  • 문제를 풀 때는 정답 코드보다 자료구조 선택 이유를 먼저 적는다.
BGM EVER