자료구조(Data Structures) 개요
자료구조(Data Structures) 개요
프로그래밍에서 데이터를 어떻게 효율적으로 저장하고 사용할 것인지는 성능에 매우 큰 영향을 미친다.
자료구조는 데이터를 메모리에 구조화하여 삽입, 삭제, 탐색, 정렬, 접근 등 다양한 연산을 최적화할 수 있도록 도와주는 기술이다.
아래는 roadmap.sh에서 제공하는 자료구조 관련 학습 항목의 개요를 정리한 것이다. 각 자료구조의 핵심 개념과 성격을 파악하고, 이후 전용 로드맵으로 학습을 이어가면 된다.
📌 기본 선형 자료구조
1. 배열 (Array)
- 메모리에 연속적으로 저장됨
- 인덱스를 통한 빠른 접근이 가능
- 크기가 고정됨 (동적 배열은 예외)
2. 연결 리스트 (Linked List)
- 요소들이 포인터로 연결되어 있음
- 삽입/삭제는 빠르지만 인덱스 접근은 느림
- 단일/이중/환형 리스트로 구분
3. 스택 (Stack)
- LIFO(Last In First Out)
push,pop연산- 함수 호출 스택 등에 사용
4. 큐 (Queue)
- FIFO(First In First Out)
enqueue,dequeue연산- 대기열, 작업 스케줄 등에 사용
📚 Queue Data Structure - Coursera
5. 해시 테이블 (Hash Table)
- 키-값 저장 방식
- 평균 시간복잡도 O(1)
- 충돌 해결: 체이닝, 오픈 주소법 등
🌲 트리(Tree) 구조
6. 트리 (Tree)
- 계층적 구조를 가지는 비선형 자료구조
- 부모-자식 관계로 구성됨
7. 이진 트리 (Binary Tree)
- 자식 노드를 최대 2개까지 가질 수 있음
8. 이진 탐색 트리 (BST)
- 왼쪽 자식 < 루트 < 오른쪽 자식
- 탐색/삽입/삭제 시 평균 O(log n)
9. 힙 (Heap)
- 완전 이진 트리 기반
- 최소/최대 힙으로 구분
- 우선순위 큐 구현에 활용
📚 Heap Data Structure - Programiz
10. 다양한 트리 형태
- 포화 이진 트리: 모든 노드가 자식 2개 또는 0개
- 완전 이진 트리: 마지막 레벨만 왼쪽부터 채워짐
- 균형 이진 트리: 서브트리 높이차 ≤ 1
- 불균형 트리: 위 조건을 만족하지 않음
🔗 그래프(Graph)
11. 그래프
- 정점(vertex)과 간선(edge)로 구성된 네트워크
- 방향 그래프(Directed) vs 무방향 그래프(Undirected)
12. 그래프 표현 방식
- 인접 행렬 (Adjacency Matrix): V x V 배열, 정적
- 인접 리스트 (Adjacency List): 각 정점마다 연결 리스트, 동적
13. 스패닝 트리 (Spanning Tree)
- 그래프 내 모든 정점을 연결하는 최소 간선 트리
- 대표 알고리즘: Kruskal, Prim
🧠 마치며
자료구조는 컴퓨터 과학의 뼈대이며, 문제 해결 능력을 결정짓는 중요한 도구이다. 위 개념들을 먼저 파악하고 나면, 이후 알고리즘 설계나 최적화 전략을 완성도 있게 진행할 수 있다.
Server Dev