자료구조란?
효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합.
복잡도
- 시간 복잡도
- 빅오 표기법: 입력 범위 n을 기준으로 로직이 몇 번 반복되는지.
의 복잡도를 갖는다면 O()으로 표시한다.
- 공간 복잡도: 프로그램을 실행했을 때 필요로하는 자원 공간.
Int타입의 arr[128]배열이 존재한다면, 128x4의 공간을 차지함.
자료 구조에서 시간 복잡도
- 평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
- 최악 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | O(n) | O(n) | O(n) | O(n) |
| AVL트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
선형 자료구조
- 연결 리스트
데이터를 감싼 노드를 포인터로 연결하여 공간적 효율성을 증대시킨 구조.
삽입과 삭제에 O(1), 탐색에 O(n)이 소요됨.
- 싱글 연결 리스트: next 포인터만 가짐
- 이중 연결 리스트: next와 prev 포인터를 가짐.
- 원형 이중 연결 리스트: next, prev 포함하며 마지막 next가 헤드 노드 가리킴.
-
배열
같은 타입의 변수를 정해진 크기의 인접한 메모리 공간에 모아 놓은 구조.
삽입과 삭제에 O(n), 탐색에 O(1)이 소요됨.
랜덤 접근에 유리한 점을 가짐. -
동적 배열
동적으로 요소를 할당할 수 있는 동적 배열.
맨 뒤, 맨 앞을 제외한 요소 삭제에 O(n), 탐색에 O(1) 소요됨.
요소를 추가하여 크기가 +1이 될 때마다 용량을 두 배로 늘림. -
스택
마지막으로 들어간 데이터가 가장 먼저 나오는 구조.
삽입 및 삭제에 O(1), 탐색에 O(n) 소요됨. -
큐
먼저 들어간 데이터가 가장 먼저 나오는 구조.
삽입 및 삭제에 O(1), 탐색에 O(n) 소요됨.
비선형 자료구조
- Graph
정점(vertex)과 간선(edge)으로 이루어진 자료 구조.
양방향, 단방향 그래프가 있음.
-
인접 행렬 방식
2차원 배열에 모든 정점들의 연결 정보를 입력하는 방식.
구현이 간단하고 연결 정보를 파악하는데 좋지만 공간이 낭비되고 시간 복잡도가 O() 소요된다. -
인접 리스트 방식
각 정점의 리스트 배열을 만들어 해당 정점과 직접 연결된 노드들을 삽입.
연결 정보 탐색에 O(n)만 소요되고 공간의 낭비가 적지만 특정 두 점이 연결되었는지 확인하기 어렵다.
- Tree
그래프 중 하나로 정점과 간선으로 이루어졌고 트리 구조로 배열됨(사이클X).
부모, 자식을 가지고 임의의 두 노드 사이 경로가 반드시 하나 존재하는 특징을 가짐.
용어)
깊이: 루트 노드(0)에서 특정 노드까지 최단 거리로 갔을 때 거리
높이: 루트 노드(0)부터 리프 노드까지 거리 중 제일 긴 거리
레벨: 깊이와 유사함. 루트 노드를 0 또는 1로 정하여 표현.
-
이진 트리 (Binary Tree)
자식의 노드 수가 두 개인 트리.- full binary tree: 자식노드 0개 또는 2개
- complete binary tree: 왼쪽부터 채워진 이진 트리
- perfect binary tree: 모든 노드 꽉 차있는 이진 트리
- balanced binary tree: 왼쪽과 오른쪽의 높이 차이가 1 이하.
-
이진 탐색 트리 (Binary Search Tree)
현재 노드의 왼쪽에는 현재 값보다 작은 값들만, 오른쪽에는 현재 값보다 큰 값들만 존재하는 이진 트리.
일반적으로 탐색 시 O(logn)이 걸리지만 선형적인 경우 O(n). -
AVL트리
이진 탐색트리처럼 선형적인 트리가 되는 것을 방지.
왼쪽과 오른쪽의 높이 차이가 최대 1인 균형잡힌 이진 트리.
높이 차이가 1보다 커지면 rotation 작업을 통해 균형을 맞춤.
균형 판단: 현재 노드의 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 정보를 저장하고, 해당 값이 -1, 0, 1 중에 없다면 균형이 무너진 것으로 판단한다.
-
레드 블랙 트리
이진 탐색트리처럼 선형적인 트리가 되는 것을 방지.
왼쪽과 오른쪽의 높이 차이가 최대 1인 균형잡힌 이진 트리.
다음의 규칙을 기반으로 재배치하여 균형을 잡는 트리이다.- 모든 노드들은 검은색 또는 빨간색이며 루트, 리프 노드는 검은색.
- 빨간색 노드의 자식은 검은색이다. (No double red)
- 루트 노드부터 모든 리프노드까지의 검은 노드 개수가 같다.
- Heap
이진 트리 기반이며 최대힙, 최소힙으로 나뉜다.
- 최대힙: 루트 노드의 키가 모든 자식들의 키보다 큼. (루트가 제일 큼)
- 최소힙: 루트 노드의 키가 모든 자식들의 키보다 작음. (루트가 제일 작음)
(두 힙 모두 해당 특성이 자식 노드들도 재귀적으로 만족)
최대힙의 삽입 과정
- 새로운 노드를 힙의 마지막 노드에 삽입.
- 해당 노드부터 루트 노드로 올라가며 비교해 교환.
최대힙의 삭제 과정
- 루트 노드를 삭제.
- 빈 루트 자리에 마지막 노드를 넣고 자식 노드들과 비교하며 교환.
-
Priority Queue
대기열에서 우선순위가 높은 요소가 낮은 요소보다 먼저 제공되는 구조.
힙을 기반으로 구현하며 반복적으로 루트 노드를 제공함. -
Map
특정 순서에 따라 키와 값의 조합으로 형성된 구조.
- HashMap: Hash table 기반으로 저장하며 순서를 보장하지 않지만 빠름.
- TreeMap: 레드 블랙 트리 기반으로 저장하며 key값을 기준으로 정렬 상태를 유지함.
- LinkedHashMap: 데이터의 입력된 순서를 기억함. Node 기반 연결 리스트 구조.
- Set
특정 순서에 따라 고유한 요소를 저장하는 구조(중복 없음)
- HashSet: HashCode 기반으로 배열에 값을 추가.
- TreeSet: 레드 블랙 트리 기반으로 값 저장.
- Hash Table
데이터를 유한한 개수의 해시 값으로 매핑한 테이블.
