배열 vs 연결 리스트
항목 | 배열 (Array) | 연결 리스트 (Linked List) |
메모리 구조 | 연속된 공간 | 노드 + 포인터 |
접근 속도 | 빠름 (O(1)) | 느림 (O(n)) |
삽입/삭제 | 느림 (중간: O(n)) | 빠름 (O(1) 또는 O(n)) |
활용 | 인덱스 기반 접근 | 삽입/삭제 많은 구조 |
스택(Stack) & 큐(Queue)
스택
•
LIFO (Last In, First Out)
•
연산: push(), pop(), peek()
•
활용: DFS, 함수 호출 스택, 괄호 검사
큐
•
FIFO (First In, First Out)
•
연산: enqueue(), dequeue(), peek()
•
활용: BFS, 작업 대기열, 캐시 구조
변형 구조: Deque (Double-Ended Queue) → 앞뒤 삽입/삭제 모두 O(1)해시 테이블 (Hash Table)
•
키-값 쌍으로 데이터를 저장
•
평균 시간 복잡도: 검색/삽입/삭제 → O(1)
•
내부 구조: 배열 + 해시 함수 + 체이닝(충돌 해결)
활용: HashMap, Set, 카운팅/중복 제거/빈도 분석
트리 (Tree)
•
계층적 구조 (부모-자식 관계)
•
이진 트리(Binary-Tree): 자식이 최대 2개
•
이진 탐색 트리(BST): 왼쪽 < 루트 < 오른쪽
•
순회 방식: 전위/중위/후위 탐색
힙(Heap)
•
완전 이진 트리, 항상 정렬된 구조 유지
•
최소 힙: 부모 ≤ 자식
•
최대 힙: 부모 ≥ 자식
•
활용: 우선순위 큐, 힙 정렬
그래프(Graph)
•
정점(Vertex) + 간선(Edge)으로 구성된 구조
•
방향/무방향, 가중치/비가중치 구분
•
표현 방식: 인접 행렬, 인접 리스트
주요 탐색 알고리즘
•
DFS: 스택/재귀 기반 (깊이 우선)
•
BFS: 큐 기반 (너비 우선)
활용 예: 소셜 네트워크, 지도 경로, 네비게이션트라이(Trie)
•
문자열을 저장하는 트리형 구조
•
각 노드는 문자 하나를 표현
•
활용: 자동완성, 접두사 검색
시간 복잡도 요약표
자료구조 | 삽입 | 삭제 | 탐색 |
배열 | O(n) | O(n) | O(1) |
연결리스트 | O(1)/O(n) | O(1)/O(n) | O(n) |
스택/큐 | O(1) | O(1) | O(n) |
해시 테이블 | O(1) | O(1) | O(1) |
힙 | O(log n) | O(log n) | O(n) |
BST | O(log n) | O(log n) | O(log n) |
그래프 탐색 | - | - | O(V + E) |