[C++] STL 정리

Pair

- pair를 사용하면 두 자료형 T1과 T2를 묶을 수 있음

- 첫번째 자료는 first , 두번째 자료는 second로 접근!

- make_pair() 를 통해 만들 수 있다

- #include <algorithm> or #include <vector>

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl;
    
    p1 = make_pair(10,20);
    cout << p1.first << ' ' << p1.second << endl;
    
    p1 = pair<int, int>(30,40);
    cout << p1.first << ' ' << p1.second << endl;
}

Tuple

- pair와 같지만 여러개를 묶을 수 있다

- make_tuple() 으로 만들 수 있음

- 인덱스를 통해 접근 가능

- get<index>(tuple)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    tuple<int,int,int> t1 = make_tuple(1,2,3);
    
    cout << get<0>(t1) << ' ';
    cout << get<1>(t1) << ' ';
    cout << get<2>(t1) << endl;
}
 

Vector

- vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 자주 사용함

- 길이를 변경 할 수 있는 배열

- vector<vector<int>> v 로 선언하여 2차원 배열로 사용 가능

- v.push_back()        // data 추가

- v.pop_back()         // data 삭제

- v.clear()                // 벡터 초기화

- v.size()                 // 벡터의 크기

- v.empty()             // 벡터가 비었는지 확인 ( true or false )

- v.front()               // 벡터의 첫번째 원소

- v.back()                // 벡터의 마지막 원소

- v.insert(v.begin(), 5, 0)        // vector의 첫번째원소 앞에 0을 5개 삽입

- v.erase(v.begin()+2)            // vector의 첫번째원소에서 2만큼 옆에 있는 원소를 삭제

# Iterator를 사용하여 벡터 출력

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    vector<int> v = {1,2,3,4,5};
    
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it){
        cout << *it << ' ';
    }
    cout << endl;
    
    for(auto it=v.begin(); it!=v.end(); ++it){
        cout << (it-v.begin()) << ": " << *it << endl;
    }
}

# Vector 원소를 출력해주는 함수

void printVector(vector<int> &v){
    for(int x: v){
        cout << x << ' ';
    }
    cout << endl;
}

Deque

- 벡터와 비슷한 컨테이너지만 벡터의 메모리 할당 단점을 보완

- Vector는 새로운 원소를 삽입할 때 할당된 메모리가 부족하면 이전 메모리 블록을 삭제하고, 새로운 메모리 블록을 재할당하며 이전 원소를 모두 복사

- Deque은 새로운 단위의 메모리 블록을 할당하고 원소를 삽입

- 또한, 새로운 원소를 순차열 중간에 삽입, 제거 하더라도 원소의 개수가 작은쪽으로 밀어냄

- 시작과 끝에서 삽입, 삭제 가능

- d.push_back()         // data 추가 (끝에서)

- d.push_front()        // data 추가 (시작점에서)

- d.pop_back()         // data 삭제 (끝에서)

- d.pop_front()         // data 삭제 (시작점에서)

📝10866번 문제 (덱)

🔥String 비교시 == 과 compare 의 차이점??

🔥문자열 입력 시 cin 과 getline 의 차이점??

List

- List 컨테이너는 vector와 deque처럼 시퀀스 컨테이너로 원소가 상대적인 순서를 유지함

- 그러나 list는 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스트로 구현된다

- l.sort()                                // 오름차순 정렬

- l.sort(greater<int>())          // 내림차순 정렬

📝2346번 문제 (풍선 터뜨리기)

📝1406번 문제 (에디터)

🔥단항연산자 ++, -- 를 iterator에 사용할 경우의 차이점

🔥list에서 현재 가르키는 iterator를 insert, erase 하는 것

if(cursor!=editor.begin()){
    auto tmp = cursor;
    --cursor;
    editor.erase(cursor);
    cursor = tmp;
}

Set

- set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 value의 집합으로 이루어진 컨테이너이다

- 모든 연관 컨테이너는 노드 기반 컨테이너이며 균형 이진트리로 구현되므로 균형 이진트리의 모든 특징을 갖는다

- key의 집합이기 때문에 중복값을 허용하지 않음!!

- s.erase(it)        // 원소삭제  - 삭제를 하면 다음 노드를 가르킴

Map

- map 컨테이너는 연관 컨테이너 중 자주 사용하는 컨테이너로 원소를 key, value 쌍으로 저장한다

- set 은 원소로 key 하나만을 저장하지만, map 은 key, value 를 저장한다

- map 또한 중복 key 허용하지 않는다 ( 만약 중복 key를 저장해야 한다면 multimap 사용 )

📝1076번 문제 (저항)

📝1764번 문제 (듣보잡)

🔥

Stack

- 컨테이너 어댑터의 종류는 Stack, Queue, Priority_queue가 있다

- 그 중, 대표적인 컨테이너 어댑터는 stack 이다

- LIFO 방식의 시퀀스

- empty, size, push_back, pop_back, back 의 인터페이스를 지원하는 컨테이너는 모두 stack 컨테이너 어댑터를 사용하여 스택으로 변환 가능

- s.push()

- s.pop()

- s.top()

- s.empty()

Queue

- Stack 과는 다른 FIFO 방식의 시퀀스

- BFS (Breadth First Search, 너비우선탐색)

- q.push()

- q.pop()

- q.front()

- q.back() 

📝1158번 문제 (조세퍼스 문제)

Priority_queue

- Queue가 FIFO 방식인 반면, Priority_queue는 빠지는건 최소, 혹은 최대부터 !!

- push 와 pop이 O(log n) 시간에 처리된다

- 최대부터 빠지는 힙을 Max Heap , 최소부터 빠지는 힙을 Min Heap 이라 한다

📝1927번 문제 (최소 힙)

그래프 탐색

개념

- DFS : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

- BFS : 현재 정점에 연결된 가까운 점들부터 탐색

구현

- DFS : 스택 또는 재귀함수로 구현

- BFS : 큐를 이용해서 구현

# DFS (Recursion)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// dfs에 들어오면 '방문'한거로 판단
// 해당 위치에 check true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
    check[start]= true;
    printf("%d ", start);
 
    for(int i=0; i < graph[start].size(); i++){
        int next = graph[start][i];
        // 방문하지 않았다면
        if(check[next]==false){
            // 재귀함수를 호출한다.
            dfs(next, graph, check);
        }
    }
}
 
int main (){
 
    int n, m, start;
    cin >> n >> m >> start;
 
    vector<int> graph[n+1];
    bool check [n+1];
    fill(check, check+n+1, false);
 
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
 
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    // Sorting은 왜 한거지?
    // 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
 
    //dfs
    dfs(start, graph, check);
    printf("\n");
 
    return 0;
}

# DFS (Stack)

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>
 
using namespace std;
 
 
// stack에 들어가면 방문한거로 판단
// 해당 위치를 true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
 
    stack<int> s;
    s.push(start);
    check[start] = true;
    printf("%d ",start);
 
    while(!s.empty()){
 
        int current_node = s.top();
        s.pop();
        for(int i=0; i<graph[current_node].size(); i++){
 
            int next_node = graph[current_node][i];
 
            if(check[next_node]==false){
                printf("%d ", next_node);
                check[next_node] = true;
                // pop()을 했었기 때문에 현재 current_node도 넣어줘야한다.
                s.push(current_node);
                s.push(next_node);
                break;
            }
        }
    }
 
}
 
int main (){
 
 
    int n, m, start;
    cin >> n >> m >> start;
 
    vector<int> graph[n+1];
    bool check [n+1];
    fill(check, check+n+1, false);
 
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
 
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    // Sorting은 왜 한거지?
    // 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
 
    //dfs
    dfs(start, graph, check);
    printf("\n");
 
    return 0;
}
 

# BFS

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
void bfs(int start, vector<int> graph[], bool check[]){
    queue<int> q;
 
    q.push(start);
    check[start] = true;
 
    while(!q.empty()){
        int tmp = q.front();
        q.pop();
        printf("%d ",tmp);
        for(int i=0; i<graph[tmp].size(); i++){
 
            // 방문하지 않았다면
            if(check[graph[tmp][i]] == false){
                // 큐에 넣어주고 방문했음을 표시한다.
                q.push(graph[tmp][i]);
                check[graph[tmp][i]] = true;
            }
        }
    }
 
}
 
int main (){
 
    int n, m, start;
    cin >> n >> m >> start;
 
    vector<int> graph[n+1];
    bool check [n+1];
    fill(check, check+n+1, false);
 
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
 
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    // Sorting은 왜 한거지?
    // 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
 
    //bfs
    bfs(start, graph, check);
    printf("\n");
 
    return 0;
}