AIINSIGHT NOTE
AI · Web3 · Tech trends and insights at a glance
자료구조
편집데이터를 효율적으로 저장·조회·수정하기 위한 구조와 알고리즘의 기반. 배열·연결 리스트·스택·큐·트리·그래프·해시맵·힙 등 핵심 자료구조의 원리와 구현, 시간복잡도를 다룬다.
자료구조(Data Structure)는 데이터를 효율적으로 저장하고 접근·수정할 수 있도록 체계적으로 조직하는 방법이다. 어떤 자료구조를 선택하느냐에 따라 알고리즘의 시간복잡도와 공간복잡도가 결정되며, 올바른 선택이 소프트웨어 성능의 핵심이다.
왜 자료구조를 알아야 하는가?
같은 문제도 자료구조에 따라 해결 속도가 크게 달라진다.
| 연산 | 배열 | 해시맵 | 이진 탐색 트리 |
|---|---|---|---|
| 탐색 | O(n) | O(1) | O(log n) |
| 삽입 | O(n) | O(1) | O(log n) |
| 정렬된 순회 | O(n log n) | 불가 | O(n) |
올바른 자료구조를 선택하는 것이 알고리즘 최적화의 출발점이다.
주요 자료구조
선형 자료구조
| 자료구조 | 핵심 특성 | 주요 용도 |
|---|---|---|
| 배열 (Array) | 인덱스 O(1) 접근, 연속 메모리 | 캐시 효율적, 정적 데이터 |
| 연결 리스트 (Linked List) | 동적 크기, O(1) 앞 삽입/삭제 | LRU 캐시, OS 프로세스 관리 |
| 스택 (Stack) | LIFO — 마지막 삽입이 먼저 제거 | 함수 호출, 괄호 검사, DFS |
| 큐 (Queue) | FIFO — 먼저 삽입이 먼저 제거 | 작업 대기열, BFS, 메시지 큐 |
| 덱 (Deque) | 양방향 삽입·삭제 | 슬라이딩 윈도우, LRU 캐시 |
비선형 자료구조
| 자료구조 | 핵심 특성 | 주요 용도 |
|---|---|---|
| 해시맵 (HashMap) | 키-값 매핑, 평균 O(1) 탐색 | 캐시, 빈도 계산, 중복 제거 |
| 힙 (Heap) | 완전 이진 트리, 최대/최소 O(1) 조회 | 우선순위 큐, 다익스트라, 힙 정렬 |
| 이진 트리 (Binary Tree) | 계층 구조, 순회 방식 다양 | BST, 힙, Huffman 코딩 |
| 트라이 (Trie) | 문자열 접두사 트리 | 자동완성, 사전 검색 |
| 그래프 (Graph) | 정점과 간선의 관계 표현 | 네트워크, 경로 탐색, 소셜 그래프 |
| 세그먼트 트리 | 구간 쿼리·업데이트 O(log n) | 범위 합, 범위 최솟값 쿼리 |
시간복잡도 Quick Reference
| 자료구조 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|
| 배열 | O(n) | O(n) | O(n) |
| 연결 리스트 | O(n) | O(1)* | O(1)* |
| 해시맵 | O(1) avg | O(1) avg | O(1) avg |
| 이진 탐색 트리 | O(log n) avg | O(log n) avg | O(log n) avg |
| 힙 (최솟값 추출) | O(1) | O(log n) | O(log n) |
| 트라이 | O(L) | O(L) | O(L) |
*앞/뒤 삽입 시 (탐색 제외) L = 문자열 길이
