자료구조 요점정리

주요 알고리즘

sort(arr, arr+5, greater<int>());

sort(v1.begin(),v1.end(),greater<int>());

---

1. 일반 배열

- 선언

int arr[4] = {1,2,3,4};

- 인덱싱

arr[2];

- 2차원 선언

arr[2][3];

2. 동적 배열

- 선언

int * arr = new int[3];

2차원 배열 선언

int ** arr = new int * [10];

for(int i = 0 ; i < 10 ; i++){

arr[i] = new int[15];

}

3. 벡터

- 선언

vector<int> arr1;

같은 값으로 미리 채운다

vector<int> arr1(10 , 123); // 갯수, 숫자

- 인덱싱

arr1[2]

arr1.at(2);

- 삽입

arr1.push_back(12);

arr1.insert(arr1.begin()+i, 12); // i번째 인덱스 "앞에" 끼워넣어서 새로운 벡터의 i번째가 된다.

arr1.insert(arr1.end(),arr2.begin(),arr2.end()); // arr1 맨 뒤에 arr2 전체를 끼워 넣는다.

- 삭제

arr1.erase(arr1.begin()+1) // 1번째 인덱스를 삭제

arr1.erase(arr1.begin()+2, arr1.begin()+5); // 2 ~ 4번째 인덱스를 삭제(마지막꺼는 삭제 x)

arr1.clear() // 전체 삭제

- 공간 확보

arr1.reserve(100);

- 참고 사항

 * 벡터 대소비교 및 등호 사용 가능하다!! 앞에서부터 lexiographically 비교한다.

4. 스택

- 선언

stack<int> arr1;

- 인덱싱

arr1.top();

- 삽입

arr1.push(12);

- 삭제

arr1.pop(); // void return이므로 top으로 쓰고 팝 할것

5. 큐

- 선언

queue<int> arr1;

- 인덱싱

arr1.front();

arr1.back();

- 삽입

arr1.push(12)

-삭제

arr1.pop();

6. 우선순위 큐(힙)

- 선언

priority_queue<int> arr1; // max heap

priority_queue<int, vector<int>, greater<int>> arr1; // min heap

- 인덱싱

arr1.top()

- 삽입

arr1.push(12)

- 삭제

arr1.pop()

7. 스트링

- 띄어쓰기 포함 입력받기

getline(cin, name);

- 선언

string s;

- 인덱싱

s.at(1);

s[1];

- 삽입

s.push_back(char)

s.append(string variable)

s.insert(s.begin()+2, 'b');

- 삭제

s.erase(5) // 5 부터 쭉 삭제

s.erase(s.begin()+5) // 5만 딱 삭제

s.erase(5,9) // 5부터 시작해서 딱 9개 삭제

s.erase(s.begin()+5,s.begin()+9) // 5부터 시작해서 8까지 삭제

- 부분스트링 찾기

s.find(t); >> 찾으면 해당 인덱스 반환 못 찾으면 -1 반환

O(N)

- 부분 들어내고 딴걸로 바꾸기

s.replace(9,5,t); >> 9 10 11 12 13 5개 들어내고 t로 채우기(더 길어도 됨)

O(N)

- 스트링을 정수형으로

int z = stoi("132323");

- 참고 사항

* 스트링은 별도 counting sort를 만들면 O(k)로 정렬 가능하다!!

8. 리스트

- 선언

list<int> arr;

- 삽입

s.insert(advance(s.begin(),3),3);

- 삭제

s.erase(it);

- 인덱싱

s.front()

*it

9. 맵

map

multimap

unordered_map

unordered_multimap

앞 두개는 BST, 뒤 두개는 Hash table

- 선언

map<int,int> arr

multimap<int,int> arr

unordered_map<int,int> arr

unordered_multimap<int,int> arr

- 삽입

arr.insert(key) // arr.insert(23)

- 인덱싱

arr.find(23) >> returns iterator

arr.equal_range(23) >> returns iterator start, end ( end iterator은 그 자신은 포함 안하고 하나 앞까지가 진짜다 )

발견 못하면 end(), end() 반환함

arr.lower_bound(2) >> 2를 포함해서 더 큰 첫 index 반환

arr.upper_bound(2) >> 2보다 더 큰 첫 index 반환(2를 포함 x)

-- 이것들은 set,map,multiset,multimap에만 있다. 대소비교가 가능해서. O(logN).

- 삭제

arr.erase(itlow,itup) // itlow ~ itup-1 까지 삭제

arr.erase(23) // 23 키를 가진 것 삭제 ( multi 에서는 그 키 전부 삭제 )

- 순회

#include <unordered_set>
 
using namespace std;
 
int main(){
    unordered_set<int> tmp;
    for(auto it = tmp.begin() ; it != tmp.end() ; it++){
        cout << *it << endl;
    }
}
 

- 참고 사항

 * 만약 multiset 같은데서 각 키별로 뭘 할 일이 있으면 set을 하나 더 써서 같이 삽입하면 된다.

 * find는 multi에서는 첫 번째 입력했던 value를 반환한다. 하나만.

 * map에서 iterator은 pair이므로 it->first, it->second 사용

 * multimap, multiset 은 모두 key 만 정렬해주고 value는 정렬 안해준다!!!

10. 셋

set

multiset

unordered_multiset

unordered_set

사실상 맵과 같다.

11. 이터레이터

큐, 스택, priority_queue에는 없다. 아예 업음!!

vector<int>::iterator it = arr1.begin() // 이게 정식 변수명

advance(it, -3) // 앞으로 3개 전진한다.

begin(arr), end(arr) // 앞뒤 원소의 이터레이터를 내놓는다.

it = it + 3 // +- 연산자는 벡터, 스트링에 있는데 나머지에는 없다. ++, -- 만 존재.

front, back >> vector, list 에는 존재. queue, stack, map 류에는 안 존재.

- 참고 사항

 * 클래스 간 대소비교를 하는데, STL 클래스들은 이터레이터를 순회하면서 개별 대소비교를 하는 것 같다. 즉 operator > < == 사용 가능!

11. back, front

list, vector, queue에 존재

stack, priority_queue에는 아예 없음

** 참고 사항

- 벡터나 셋 등도 전부 클래스인데, 클래스를 인자로 넣으면 전부 call by value로 원본 값에 레퍼런스 하지 않는다. 원본 값을 변경하고 싶으면 * 나 &을 쓰자. 근데 &는 참조 변수로 그 변수 자체가 그 값을 가리키는 별명인데, 포인터 변수는 그야말로 주소값 변수이다.

** 기타 내용

- 함수 인자에 const를 붙이는 경우 밖에서 거기에 const 아닌걸 넣는건 괜찮은데, 함수 내에서 그 인자의 값을 바꿀 수 없다.