자료구조

데이터들과의 관계, 함수, 명령 등의 집합

자료구조는 선형 자료구조와 비선형 자료구조로 구분된다.

• 선형 자료구조 : 데이터들이 한 줄(1차원)로 나열되는 구조
  • Array
  • Stack
  • Queue
  • Linked-list
• 비선형 자료구조 : 데이터가 1차원 직선으로만 이어지지 않고, 계층/그물(그래프)처럼 여러 방향으로 연결되는 구조
  • Graph
  • Tree

1. array (정적 배열)

컴파일 시점에 크기 정해지고, 프로그램 실행중에 크기가 변하지 않는다.

또한, 메모리에서 연속적으로 공간이 할당된다.

vector와 다르게 별도의 함수가 존재하지 않는다.

2. vector (동적 배열)

동적으로 요소를 할당할 수 있는 동적 배열 (컴파일 시점에 크기를 모르는 경우 사용)

또한, 메모리에서 연속적으로 공간이 할당된다.

사용해야 할 요소들의 개수를 모를때 -> 주로 vector를 사용한다

(1) 초기화

vector<int> v; //빈 벡터 선언
vector<int> v{1,2,3}; //1,2,3으로 채우기
vector<int> v(5,100); //칸 5개 만들고 전부 100으로 채우기

(2) 접근

v[2] 와 같이 인덱스로 접근이 가능하다

(3) 주요 함수

vector<int> v;
v.push_back(넣을 값) //O(1)
v.pop_back() // O(1)
v.erase(삭제할 요소를 가리키는 이터레이터) //O(n)  뒤에거 당겨야하니까
v.erase(첫 번째 이터레이터, 마지막 그 다음 이터레이터); //O(n)   뒤에거 당겨야하니까
find(첫 번째 이터레이터, 마지막 그 다음 이터레이터, 찾을 값); // O(n)  최악의 경우 전부 탐색
v.clear() // O(n) 전부 삭제하니까
fill(첫 번째 이터레이터, 마지막 그 다음 이터레이터, 초기화 값); O(n)
(int)v.size() // v의 크기 반환 (요소의 개수) !!int로 형 변환 꼭 해주기 !! O(1)

• 탐색(랜덤 접근)의 시간 복잡도
  • 벡터는 메모리에 연속으로 저장되므로 -> 벡터의 크기가 얼마이든 시작 주소에서 덧셈 한 번으로 랜덤 접근이 가능하다. -> O(1)
• 맨 뒤 삽입 (push_back)의 시간 복잡도
  • 벡터는 size(실제 원소수)를 따로 관리하고있음 -> 벡터의 크기가 얼마든 맨 뒤에 그냥 쓰면됨 -> O(1)
• 맨 뒤 삭제 (pop_back)의 시간 복잡도
  • 벡터의 크기가 얼마든 size(실제 원소수)만 1 감소 시키면됨 -> O(1)
• 중간 삭제 (erase)의 시간 복잡도
  • 중간에 애들 삭제 -> 뒤에 애들을 앞으로 당겨야함 -> 시간복잡도 O(n)

(4) 2차원 배열

vector<vector<int>> v1;
vector<vector<int>> v2(5,vector<int>(8,0));
vector<int> v3[5];; //

int main() {
	for(int i=0;i<5;i++) {
    	vector<int> tmp;
        v.push_back(temp);
    
    }


	return 0;
}

3. 연결 리스트 (Linked List)

요소가 인접한 메모리 위치에 저장되지 않는 선형 자료구조

(1) 이중 연결 리스트 (Double Linked List)

C++에서는 list<타입> 으로 이중 연결 리스트를 쉽게 사용할 수 있다.
(std::list는 Head와 Tail을 전부 유지하는 구조체임을 명심하자)

특징

랜덤 접근이 불가능하고, 오로지 순차적 접근만 가능하다.

벡터는 연속 메모리를 할당 받는다. 반면 연결 리스트는 비연속적으로 메모리를 할당받는다. (메모리가 비연속적이지만, Next와 Prev가 노드들을 포인터로 연결해준다)

3번째 노드에 접근하려면?

HEAD → [10] → [20] → [30] ← 여기까지 하나씩 따라가야 함
  1번      2번      3번

따라서 앞의 노드를 전부 순차적으로 거쳐서 포인터 타고 타고 타고 가야만 뒤에 노드에 접근할 수 있다.
-> 특정 노드에 접근하는 시간복잡도가 O(n) 이다.

삽입, 삭제의 시간 복잡도가 전부 O(1) 이다.🌟🌟🌟🌟🌟🌟🌟🌟🌟

중간 삽입,삭제의 경우를 살펴보자.

연결 리스트는 벡터와 다르게 포인터로 구현되어있으므로-> 위치만 알고있다면 -> 리스트의 크기가 얼마이든 삽입, 삭제시 원소를 밀거나 당길 필요없이 포인터만 일정 횟수 수정해주면 된다 -> 시간복잡도 O(1)

맨 앞 OR 맨 끝 삽입, 삭제의 경우를 살펴보자.

std::list 는 Head와 Tail을 모두 유지한다 -> 리스트의 크기와 관계없이 항상 일정 횟수의 연산으로 삽입, 삭제가 가능하다. -> 시간복잡도 O(1)

(O(1)은 자료구조의 크기와 관계없이 일정한 횟수의 연산이 수행됨을 의미한다)

주요 코드

list<int> l1;              // 빈 리스트
list<string> l2;           // 빈 string 리스트
list<int> l1 = {1, 2, 3, 4, 5};
list<int> l2{1, 2, 3, 4, 5};        // = 생략 가능
l1.push_front(값) //리스트의 맨 앞에 값을 넣는다 O(1)
l1.push_back(값) //리스트의 맨 뒤에 값을 넣는다 O(1)
l1.insert(값을 넣을 위치를 가리키는 이터레이터, 값) //특정 위치에 값을 삽입한다 O(1)
l1.erase(값을 삭제할 위치를 가리키는 이터레이터) //특정 위치의 값을 삭제한다 O(1)
l1.pop_front() // 리스트의 첫 번쨰 요소를 지운다 O(1)
l1.pop_back() // 리스트의 맨 뒷요소를 지운다. O(1)
l1.front() // 리스트의 맨 앞 요소를 참조형으로 반환한다 O(1)
l1.back() // 리스트의 맷 뒷 요소를 참조형으로 반환한다 O(1)
l1.clear() // 리스트의 모든 요소를 지운다 O(1)
find(첫 번째 이터레이터, 마지막 그 다음 이터레이터, 찾을 값); // O(n)  최악의 경우 전부 탐색

연속 메모리 공간을 할당받는 array, vector와 다르게 비연속 메모리 공간을 할당받는 포인터 기반 이므로
-> 뒷 요소들을 밀거나 당길 필요가 없어서 -> 시간 복잡도가 전부 O(1) 이다.

• 위치 찾기까지 포함시 O(n)이나, 위의 함수들의 경우 맨 앞, 맨 뒤에 삽입, 삭제하는 애들을 Head와 Tail이 있기에 모두 위치를 알고있고, 중간에 삽입/삭제하는 애들은 인자로 이터레이터(=위치 정보)를 전달해주기 때문에 거의 모든 함수의 시간복잡도가 O(1) 이다

4. 맵 (Map)

key-value 쌍의 요소가 존재하고, ASCII Code를 기준으로 key값이 자동 정렬되는 자료구조

(1) 특징

• key값은 중복이 불가하다🌟🌟🌟🌟🌟🌟🌟🌟🌟
• key값이 ASCII 코드에따라 자동 오름차순 정렬된다🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
• 대괄호 연산자([])를 활용해 key값으로 value에 접근할 수 있다.
  • 주의 : key값으로 접근만 해도 해당 key값으로 요소가 생성된다.(value경우 자동으로 자료형별 초기값이 들어감. int의 경우 0이 들어감)🌟🌟🌟🌟🌟🌟🌟
• 균형이진트리로 구현되어있어서 탐색(접근), 삽입, 삭제가 O(logN)의 시간 복잡도를 가진다.🌟🌟🌟🌟🌟

(2) 선언

map<string, int> mp;

(3) 주요 코드

map<string, int> mp; //map 선언
mp.insert({key값, value값}) //map에 특정 key가 존재 x일때만 -> {key,value}를 map의 원소로 넣어준다 (덮어쓰기 x)
mp[key] = value // map에 {key,value}를 원소로 넣어준다. (덮어쓰기 o). 시간복잡도는 O(logN) 이다.
mp[key] //key로 value에 접근한다. (만약 key가 존재 x면 {key,초기값}이 map에 원소로 생겨난다. 시간복잡도는 O(logN) 이다. <------------중요!!!!!
(int)mp.size() //map의 원소의 개수 반환
mp.erase(key값) //map의 key값에 해당하는 원소 삭제
mp.find(key값) //map의 key값에 해당하는 원소를 가리키는 이터레이터 반환 (못 찾으면 마지막 그 다음 요소를 가리키는 이터레이터 반환) .시간 복잡도는 O(k*logN) 이다.
for(auto it:mp) //mp를 순회하는데, 이때 key는 it.first로, value는 it.second로 참조 가능🌟🌟🌟🌟🌟
for(auto it = mp.begin(); it != mp.end(); it++) //mp의 요소를 이터레이터로 순회
mp.clear() //map의 모든 요소들을 삭제

(4) 주의 사항 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

주의 : mp[key]로참조만 해도 해당 key값으로 요소가 생성되버린다.

이를 이용해서 map<string, int> mp에 key가 없음에도 mp[key]++ 하면 value 값이 1이 된다.

(5) 참조없이 map에 요소 존재하는지 확인

if(mp.find(key값) != mp.end()) { //map에 key값이 존재하는지 확인
	로직..
	로직..
}

mp[key]안쓰고 mp.find(key 값)를 활용해서 map에 요소가 존재하는지 확인할 수 있다.

5. Unordered Map

(1) 특징

• 자동 정렬이 되지않는 map 이다.
• map과 메서드가 동일하다.
• 해시테이블 기반이고 탐색(접근), 삽입, 삭제의 시간복잡도가 평균적으로 O(1), 최악의 경우 O(N)이다.

삽입, 삭제의 시간복잡도가 map보다 높다. 따라서 정렬이 필요없는 문제라도 umap 사용시 -> 시간 초과가 발생할 위험이 크므로 -> 앵간하면 map을 사용하는 것이 바람직하다.

(2) 주요 코드

unordered_map<string, int> umap; //umap 선언
umap[key] = value // map에 {key,value}를 원소로 넣어준다. (덮어쓰기 o). 시간복잡도는 O(N) 이다.

6. set

중복을 허용하지 않는 컨테이너

(1) 특징

• 원소의 중복을 허용하지 않는다.
• map처럼 {key,value}로 집어넣지 않아도 된다.
• 중복된 원소를 삽입하면 무시된다
• map과 같이 자동 정렬된다
• map과 동일한 메서드를 갖는다.

(2) 주요 코드

set<pair<string,int>> st; //원소가 pair<string,int>인 set 선언
st.insert({"test",1});

(3) vector 중복제거: set 컨테이너 vs unique(v.begin(), v.end())

vector 컨테이너의 중복 제거가 필요할때, set 컨테이너를 활용할 수도있고, unique(v.begin(), v.end())을 활용할 수도 있다.

대부분의 경우 굳이 set을 추가로 만들고 이를 다시 vector에 옮기기보다 -> 기존 벡터 기반으로 unique(v.begin(), v.end()) 로 중복을 제거하는 방식이 더욱 빠르다.

7. multiset

중복을 허용하는 자료구조

(1) 특징

• 원소의 중복을 허용한다
• map처럼 {key,value}로 집어넣지 않아도 된다.
• map과 같이 자동 정렬된다
• map과 동일한 메서드를 갖는다.
• 잘 쓰이지 않는다. 가끔씩 요소의 빈도수 계산에 사용된다.

(2) 주요 코드

multiset<int> numbers = {1,2,3,3,4,5,5,5,6};
int count_five = numbers.count(5) // 5가 몇개있는지 카운트한다.

8. Stack 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

후입선출(LIFO) 의 성질을 가진 자료구조

(1) 특징

• LIFO(Last In First Out)의 성질을 가진다
• 삽입, 삭제에 O(1) , 탐색에 O(n) 걸린다
  • 삽입, 삭제는 top에서만 가능한데 내부적으로 top을 가리키는 포인터를 유지하고있으므로 스택의 크기에 관계없이 연산 횟수가 일정하다-> O(1)의 시간 복잡도
  • 탐색의 경우는 top에서 원하는게 나올때까지 pop()을 수행해야한다. 최악의 경우 n번 pop() 해야하므로 -> O(n) 의 시간복잡도
• 주로 문자열 삭제, 아름다운 괄호만들기, 짝찾기, 교차하지 않고 와 같은 동작 또는 키워드가 등장하는 문제는 90% 정도는 stack으로 쉽게 풀 수 있다.

(2) 주요 코드

stack<string> stk;
stk.push("엄");//stack에 "엄"을 삽입
stk.push("준");//stack에 "준"을 삽입
stk.push("식");//stack에 "식"을 삽입
while(stk.size()) { //stack의 size를 반환
	cout << stk.top() << "\n"; //stack의 top에 위치한 요소를 삭제없이 접근
    stk.pop(); //stack의 top에 위치한 요소를 삭제
}

9. 힙 (Heap)

모든 노드에서부모 노드의 데이터와 자식 노드의 데이터사이에 >= 또는 <= 관계를 만족하는 완전이진트리

• 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차있는 이진트리

(1) 특징

• 2가지 종류의 힙이 존재한다
  • max heap : (부모 노드 데이터) >= (자식 노드 데이터)
  • min heap : (부모 노드 데이터) <= (자식 노드 데이터)
• 시간복잡도
  • 삽입, 삭제 : O(logN)
  • 루트조회 : O(1)
  • 원하는 값 찾기 : O(N)
    • 힙은 정렬 x. 부모-자식 간의 관계만 유지되지, 조상-자손간 대소 관계 유지 x. 따라서 전부 탐색해야함.

10. 큐 (Queue)

선입선출(FIFO)의 성질을 가진 자료구조로, 삽입은 back에서, 삭제는 front에서만 가능하다.

(1) 특징

• FIFO(First In First Out)의 성질을 가진다
• 삽입은 back, 삭제는 front에서만 가능하다.
• 삽입, 삭제에 O(1) , 탐색에 O(n) 걸린다
  • 삽입은 back, 삭제는 front에서만 가능한데 -> 내부적으로 back과 front를 가리키는 포인터를 유지하고있으므로 -> Queue 의 크기에 관계없이 연산 횟수가 일정하다 -> O(1)의 시간 복잡도
  • 탐색의 경우는 front 에서 원하는게 나올때까지 삭제를 수행해야한다. 최악의 경우 n번 삭제 해야하므로 -> O(n) 의 시간복잡도

(2) 주요 코드

queue<int> q; //queue 선언
q.push(1);  //queue에 1 삽입
q.push(2); //queue에 2 삽입
q.push(3); //queue에 3 삽입
q.pop(); // queue의 front를 삭제. 현재 front 에 1이 있으므로 -> 1을 삭제
q.size() // queue의 size를 반환. 현재 queue에 2개 있으므로 -> 2를 반환
q.front() // queue의 front에 접근. 현재 front에 2가 있으므로 -> 2에 접근 (삭제없이 접근 가능하다는 특징이 있음)

11. 우선순위 큐 (Priority Queue)

각 요소에 우선순위가 부여되어있는 큐

(1) 특징

• 우선순위 높은 요소가 우선순위 낮은 요소보다 먼저 제공된다. (더욱 top에 가깝다는 뜻)
• 전달하는 비교 함수에 따라서 내부적으로 max heap 또는 min heap으로 구현된다.
• 내부적으로 heap으로 구현되므로 삽입, 삭제는 O(logN), 최상위 요소 접근은 O(1)

(2) 주요 코드

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq1 //기본적으로 내림차순 -> 가장 큰게 top에 위치
priority_queue<int, vector<int>, greater<int>> pq2; //오름차순 -> 가장 작은게 top에 위치
priority_queue<int, vector<int>, less<int>> pq2; //내림차순 -> 가장 큰게 top에 위치

int main() {
    pq.push(3);
    pq.push(10);
    pq.push(5);

    cout << pq.top() << '\n'; // 10

    pq.pop();

    cout << pq.top() << '\n'; // 5
}

12. 덱 (Deque)

앞,뒤로 삽입,삭제,참조가 모두 가능한 자료구조

(1) 특징

• front와 back 모두 삽입,삭제가 가능하다

(2) 주요 코드

deque<int> dq; //deque을 선언
dq.push_front(1); //deque의 앞에 1을 삽입
dq.push_back(2); //deque의 뒤에 2를 삽입
int test = dq.front(); //deque의 front에 접근
test = dq.back(); //deque의 back에 접근
int size = dq.size() //deque의 size를 반환
dq.pop_back(); //deque의 back에서 1개를 삭제
dq.pop_front(); //deque의 front에서 1개를 삭제