⚡ 자료구조
🔷 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
😭 필자는 파이썬, 자바, 자바스크립트로 자료구조를 다뤄봤으니 이번엔 C++로 해본다...
📌 복잡도
🔷 시간 복잡도와 공간 복잡도로 나뉜다.
⭐ 시간 복잡도
🔷 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
- 어떠한 알고리즘의 로직이
얼마나 오랜 시간이 걸리는지를 나타내는데 쓰인다. - 보통 빅오 표기법으로 나타낸다.
ex) O(n)
#include <iostream> // 헤더 파일
using namespace std; // 네임스페이스(같은 클래스 이름 구별, 모듈화)
int n = 10; // 변수 선언
int main()
{
for(int i = 0; i < 10; i++) {
for(int j=0; j < n; j++) {
for(int k =0; k < n; k++) {
if(true) cout << k << '\n'; // 출력
}
}
}
for(int i=0; i < n; i++) {
if(true) cout << i << '\n'; // 출력
}
return 0; // 프로세스 마무리
}🖨 이 코드의 시간 복잡도는 O(n^2)가 된다.
- 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤다. 연산량이 가장 많이 커지는 n의 제곱항만을 신경쓴다.
🔷 시간 복잡도의 존재 이유
- 효율적인 코드로 개선하는데 쓰이는 척도
- 더 작은 시간 복잡도의 알고리즘을 지향해야 한다.
🔷 자료구조에서의 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | 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) |
🔷 자료구조에서의 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | 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) |
⭐ 공간 복잡도
🔷 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
- 정적 변수로 선언된 것 외에도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함
int a[1000];ex) a 배열은 1000x4바이트의 크기를 가진다.
📌 선형 자료구조
🔷 요소가 일렬로 나열되어 있는 자료구조
⭐ 연결 리스트
🔷 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
- 맨 앞의 노드를 헤드(head)라 하며 포인터와 연결에 따라 종류를 구분한다.
1)싱글 연결 리스트: next 포인터만 가진다.
2)이중 연결 리스트: next 포인터와 prev 포인터를 가진다.
3)원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드를 가리킨다.
🖥 이중 연결 리스트 구현
// 연결리스트 구조체
struct node {
node* next;
node* prev;
int data;
};
node* init(node* tmp) {
tmp = new node();
tmp->prev = NULL;
tmp->next = NULL;
tmp->data = 0;
return tmp;
}
node* insert(node* head, int data) {
if (head == NULL) { // 첫 삽입인 경우
head = init(head);
head->data = data;
head->next = head; // 다음 노드를 자신으로 설정
head->prev = head; // 이전 노드도 자신으로 설정
return head;
}
node* last_node = head->prev; // head의 prev는 마지막 노드를 가리킴
node* new_node = NULL;
new_node = init(new_node); // 새로운 노드 생성
last_node->next = new_node; // 현재 마지막 노드에 생성된 노드 연결
new_node->prev = last_node; // 생성된 노드의 이전 노드를 연결
new_node->next = head; // 마지막 노드의 다음을 헤드와 연결
head->prev = new_node; // 헤드의 이전 노드를 새로만든 노드를 가리킴
new_node->data = data;
return head;
}
int getData(node* head, int index) {
node* cur_node = head;
for (int i = 0; i < index; i++) {
cur_node = cur_node->next;
if (cur_node == head) { // 다시 head로 오면 인덱스를 벗어난 것이다
break;
}
}
if (cur_node == NULL) {
return -1; // 범위를 넘어감
}
return cur_node->data;
}
node* remove(node* head, int index) { // index 번째 위치한 노드 삭제
node* cur_node = head;
for (; index; index --) {
cur_node = cur_node->next;
if (cur_node == head) { // 다시 head로 오면 인덱스를 벗어난 것이다
break;
}
}
if (index) { // 범위를 벗어남
return head; // 아무것도 안함
}
if (cur_node->prev == cur_node->next) { // 이전 노드와 다음 노드가 같은 경우
return init(head); //노드가 head뿐인 경우 head 초기화 후 반환
}
cur_node->prev->next = cur_node->next; // 현재노드의 이전노드의 다음은 현재노드의 다음노드
cur_node->next->prev = cur_node->prev; // 현재노드의 다음노드의 이전은 현재노드의 이전노드
if (cur_node == head) { // 지우는 노드가 head라면
head = head->next; // 다음 노드를 헤드로 지정
}
return head;
}// 생성, 초기화, 사용 방법
void print(node* head) {
node* cur_node = head;
while (1) {
cout << cur_node->data << " ";
cur_node = cur_node->next;
if (cur_node == head) {
break;
}
}
cout << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
node* list = NULL;
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 3);
list = insert(list, 2);
list = insert(list, 1);
print(list);
list = remove(list, 0);
print(list);
list = remove(list, 3);
print(list);
list = remove(list, 4);
print(list);
}c++은 처음인지라 이 분을 참고했다...
⭐ 배열
🔷 상자를 순서대로 나열한 데이터 구조
🤦♀️ 배열은 이제 다 알잖아...?
자바스크립트
#include <iostream>
using namespace std;
int a[10];
int main()
{
for(int i = 0; i < 10; i++) a[i] = i;
for(auto it : a) cout << it << " ";
cout << '\n';
return 0;
}
⭐ 벡터
🔷 동적으로 요소를 할당할 수 있는 동적 배열
- 컴파일 시점에 개수를 모른다면 벡터를 쓰는게 맞다.
- 중복을 허용하고 순서가 있으며 랜덤 접근이 가능하다.
💡 근데 수많은 언어와 프레임워크와 라이브러리를 다뤄봤지만 실전에서 벡터는 안썼다. 어떤 자료구조 수업을 듣던 간에 벡터는 쓸일이 없다는게 주류 의견...
선형 자료구조에는 이 외에 스택과 큐가 더 있지만 넘어간다.
(이제는 모르면 안되는 것들)
📌 비선형 자료구조
🔷 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조
- 그래프, 트리, 이진 트리, 이진 탐색 트리, AVL 트리, 힙, 우선순위 큐, 맵(map), 셋(set), 해시 테이블 등이 있다.
C로 다루기에 너무 빡세다. C++ 뉴비에게는 너무 가혹한 시련이다. 그래서 자바스크립트와 자바로 설명한 이전 포스팅으로 대체한다...
Hodie mihi, Cras tibi