그래프 인접행렬
그래프의 정점을 2차원 배열로 표현하는 인접행렬
무방향 그래프: 양방향으로 이동이 가능하고 인접행렬 구조에서 대칭행렬을 이룬다
- 2차원 배열안의 모든 정점들의 간선 정보가 있기 때문에 두 정점을 연결하는 간선을 조회할때 시간복잡도가 O(1)
- 간선의 수와 무관하게 무조건 n² 크기의 2차원 배열이 필요
- 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야해서 O(N)
-> 간선이 몇개 없는데 정점의 수가 많을 경우, 2차원 배열의 크기가 커지고 남는 공간이 많아져 메모리가 낭비되어 비효율적이다
-> 반대로 간선의 수가 많으면 좋을듯
그래프 인접리스트
간선의 수가 적은 최소 그래프에서 효과적이다
공간복잡도가 O(V + E) (정점 수 + 간선 수)
간선 탐색시간은 O(E) -> 인접리스트를 순차적으로 탐색하기 때문에 간선 수 만큼
간선 추가/삭제 = O(1)
- 모든 간선의 수를 확인하려면 head부터 순차적으로 탐색해야해서
시간복잡도가 O(N + E)
배열
연속적인 메모리 공간에 데이터를 저장하는 자료구조
메모리 사용이 효율적
- 요소를 인덱스를 사용해 바로 접근이 가능함 탐색 O(1) 상수시간
- 요소의 삽입/삭제가 느리다 O(N)
-> 안에 들어있는 요소를 모두 이동시켜야하기 때문
벡터
배열과 비슷한 느낌을 가진 동적 배열이다
크기가 동적으로 확장될 수 있는 동적배열 기반의 구조
배열과 비슷하게 요소의 삽입/삭제가 느리다
인덱스를 통해 바로 접근이 가능하다 탐색 O(1) 상수시간
- size는 현재 벡터에 들어있는 원소의 수 (실제 사용되고 있는 크기)
- capacity는 할당된 전체 메모리 공간의 크기
size가 capacity 용량을 초과하게 되면 새 배열에 새 메모리를 할당하고 기존 데이터를 복사해야 하기 때문에 메모리 재할당 비용이 발생한다
원형 연결리스트
- 원소의 삽입/삭제 O(1) 상수시간이 걸린다 (포인터로 다음 노드를 알고 있기 때문)
* 원소의 탐색은 O(N)이 걸린다. 노드가 N개 있을때 N번째 요소까지 순차적으로 들어가야하기 때문
양방향 연결리스트
- 원소의 삽입/삭제 O(1) 상수시간이 걸린다
- 원소의 탐색은 O(N)
-> 하지만 head와 tail을 탐색해야하는데, head와 tail을 알 경우 O(1) 상수시간 - 포인터 2개 사용하기 때문에 메모리 사용이 크다
단일 연결리스트
- 원소의 삽입/삭제 O(1) 상수시간이 걸린다
- 원소의 접근,탐색은 O(N)
-> 데이터 접근 시 순차적으로 진행하기 때문에 배열보다 비효율적
스택
마지막에 들어온 데이터가 가장 먼저 나가는 후입선출 구조 (LIFO)
삽입,삭제,맨위 요소 접근은 O(1)
하지만 탐색은 O(N)이다
-> 데이터에 접근 시 top부터 순차적으로 진행되기 때문
선형 큐
데이터가 뒤에서 들어오고 데이터가 앞에서 빠져나가는 구조
먼저 들어온 데이터가 먼저 나가는 선입선출 구조 (FIFO)
- 큐 안에 데이터가 다 빠진 상태에서 또 삽입을 하면 큐 오버플로우가 발생함
-> 앞부분이 비어있는 상태지만, rear가 배열의 끝에 도달하여서 이미 큐가 꽉 찬 상태로 인식되는 문제점이 있다 - 선형 큐의 시간복잡도 O(1) -> 삽입,삭제,확인이 인덱스를 통해 접근함
원형 큐 (선형큐의 문제점을 해결)
선형큐에서는 front와 rear가 계속 이동하여 rear가 가장 마지막 인덱스에 도달했을 때, 앞부분에 데이터를 더이상 삽입할 수 없어서 오버플로우가 터짐
- 원형큐에서는 포화상태와 공백상태를 구별하기 위해 한자리는 항상 비워둔다
- 인덱스로 접근하기 때문에 원형 큐의 시간복잡도 O(1)
힙 (우선스택 큐)
완전 이진트리의 한 종류로 우선순위 큐를 구현할 수 있는 자료구조
주로 최대값과 최소값을 찾아낼때 사용된다
- 우선순위 큐 : 데이터들이 우선순위를 가지고, 우선순위가 높은 데이터가 먼저 나가는 구조
- 완전 이진트리 : 왼쪽부터 차례대로 채워져있는 구조
-> 새로운 노드가 들어와도 기존 노드 순서가 유지된다는 의미
최대값이나 최소값이 root노드에 위치한다
계속 부모와 자식의 값을 비교하며 스왑한다
문자열 String
문자열 크기를 반환하는 함수 strlen() null문자는 포함하지 않는다
동적 크기 문자열을 관리하는 자료구조
문자열 추가, 비교, 문자열 크기 반환, 인덱스의 접근 가능
O(1)
해시테이블
KEY값과 VALUE값을 사용하여 데이터를 효율적으로 저장하고 검색할 수 있는 자료구조
해쉬함수를 사용하여 key값을 해시인덱스로 변환
해시충돌이 일어나서 체이닝 기법을 사용하게 될 경우 최악의 경우는 O(N)이다
-> 체이닝 기법은 주로 연결리스트를 사용하기 때문
검색,삽입,삭제가 빠르다 O(1) 상수시간
이진트리
각 노드가 최대 2개까지의 자식노드를 가진 트리
노드를 순회하는 방법은 주로 재귀함수를 사용한다
- 보통 재귀함수는 안에 있는 로직을 다 수행해야 함수가 종료된다
root를 기준으로 순회방식을 다르게 할 수 있다
- 전위순회
root -> left -> right - 중위순회
left -> root -> right - 후위순회
left -> right -> root
이진 탐색 트리
이진트리 기반의 탐색을 위한 자료구조이다
이진트리의 크기는 left < root < right 조건을 따른다
모든 서브 트리에서 적용되는 조건이다
- 시간복잡도가 O(logN)으로 탐색, 삽입, 삭제가 효율적
-> 트리구조로 깊이가 들어갈수록 반만 확인하기 때문 - 트리가 한쪽으로 치우치면 시간복잡도가 O(n)
