1. algorithm만을 위한 C++

---

I/O templete

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string temp="";
    cin >> temp;
    cout << temp;
    getline(cin,temp);
    cout << temp;
    return 0;
}

---

iterator

출처: https://eehoeskrap.tistory.com/263

• iterator에 + 할 수 있는 것은 vector, deque 뿐!

---

STL 장단점

• container 비교

Container	random access	find	insert/erase	특징
vector	$O(1)$ arr[2] arr.at(2)	$O(N)$ 순차탐색	맨앞: $O(N)$ 중간: $O(N)$ 맨뒤: $≒O(1)$	각 node가 연속적으로 할당 받음
deque	$O(1)$ dq[2] dq.at(2)	$O(N)$ 순차탐색	맨앞: $O(1)$ 중간: $O(1)$ 맨뒤: $O(1)$	deque는 여러 개의 버퍼에 데이터를 나눠 저장한다. vector는 할당된 공간이 전부 차면 배열을 다시 재할당한다. deque는 버퍼 하나만 할당하면 되므로, 데이터 삽입이 언제든 ${O(1)}$ 이다.
list	지원 X	$O(N)$ 순차탐색	맨앞: $O(1)$ 중간: $O(1)$ 맨뒤: $O(1)$	각 node가 개별적으로 메모리를 할당 받는 linked-list
set	지원 X	$O(logN)$	$O(logN)$	red black tree
map	지원 X	$O(logN)$	$O(logN)$	key-value key기준으로 정렬 됨 내부적으로 red black tree
unordered_set	-	-	-	데이터의 추가, 삭제, 접근 $O(1)$ 중복 없이 저장 정렬 X
unordered_map	-	-	-	데이터의 추가, 삭제, 접근 $O(1)$ key의 중복 허용 즉, 데이터를 여러 버킷에 나눠 저장 key가 유사한 데이터가 많을 시 성능이 떨어짐
queue	지원 X	지원 X	맨앞: $O(1)$ 중간: X 맨뒤: $O(1)$	그냥 deque 쓰는게 나을 듯
priority_queue	지원 X	지원 X	$O(logN)$	-

• container method 요약

Container	insert/erase
vector
deque
list
set
map
queue
priority_queue

---

vector

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    vector<int> arr;
    vector< vector<int> > map;
    map.resize(r);
    for(int i=0;i<r;i++){
    	map[i].resize(c);
        for(int j=0;j<c;j++){
        	cin>>map[i][j];
        }
    }
    return 0;
}

---

iterator

---

문자 -> int

---

push_back(): append

vector<int> a;
a.push_back(1);
a.push_back(2);

---

pop_back(): pop

---

erase

---

insert

vector<int> arr;
auto i = arr.begin();
arr.insert(i+1,4)

---

• 여러개 넣기
  

---

assign

vector<int> 받을대상;

받을대상.assign(from.begin(), from.begin()+X);

---

<map>

map

• C++의 map은 검색, 삭제, 삽입이 ${O(logN)}$ 인 레드블랙트리로 구성되어 있다.
• map은 내부에서 자동으로
  • key 기준으로 오름차순 정렬한다.
• map<key, value> m

#include <iostream>
#include <map>

int main(void){
	map<string, int> m;

---

insert/erase

• 없는 키를 넣으면 0 반환

---

for: 반복문

---

<unordered_map>

unordered_map

• key로 정렬하지 않는 map
  • unordered_map
  • #include ＜unordered_map＞

---

erase

• 그냥 map.erase("key값");

---

unordered_multimap

• key로 정렬하지 않는 map
  • unordered_map
  • #include ＜unordered_map＞

---

queue

queue

---

priority_queue

• 기본적으로 max heap
• q.front()가 아닌 q.top()!!!

---

pq의 cmp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
struct student {
    int id;
    int score;
};

struct cmp {
    bool operator() (student a, student b) {
        return a.score > b.score;
    }
};

int main(void) {
    priority_queue<student, vector<student>, cmp> pq;
    pq.push(student{10,100});
    pq.push(student{11,50});
    pq.push(student{12,30});

    while(!pq.empty()){
        cout << pq.top().score << ' ';
        pq.pop();
    }

    return 0;
}

---

<algorithm>

sort

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct student {
    int id;
    int score;
};

bool cmp(student a, student b) {
    return a.score > b.score;
}

int main(void) {
    vector<student> school;
    school.push_back(student{10, 100});
    school.push_back(student{11, 50});
    school.push_back(student{12, 30});
    sort(school.begin(), school.end(), cmp);
    for (int i =0; i<school.size();i++)
		cout << school[i].score << ' ';

    return 0;
}

---

stable_sort

• stable_sort는 들어온 순서를 보장한다.

#include <iostream>
#include <algorithm>

int main(void){
	/* stable_sort(begin, end, cmp); */
    // (begin, end] 까지, cmp 기준으로 들어온 순서를 보장
}

---

fill: 값 채우기

int main() {
    vector< vector<int> > vec(3, vector<int>(3));
    vector< vector<int> >::iterator iter;
    for (iter = vec.begin(); iter!= vec.end(); iter++){
        fill(iter->begin(), iter->end(), -1);
    }
}

int main() {
	vector< vector<int> > map;
    for(int i=0;i<N;i++)
    	fill(visited[i].begin(), visited[i].end(), 0);
}

---

binary search

• #include <algorithm>
  • 주어진 (시작, 종료] 까지 value를 찾으면 true, 못찾으면 false
  • 당연히 정렬된 상태의 vector에서 사용해야한다.

#include <iostream>
#include <algorithm>

int main(void){
	/* binary_search(begin, end, value);
    // [begin, end) 에서 value를 찾으면 true, 못 찾으면 false
    
    /* binary_search(begin, end, value, cmp);
    // [begin, end) 에서 value를 cmp를 기준으로 찾으면 true, 못 찾으면 false
}

• sort된 vector를 사용하여, 값의 유무를 나타낸다.
  • return 은 true | false로 나옴
  • cout 찍어보면 1 | 0

---

• cmp 사용
  

1. cmp 로 sort된 vector를 사용
2. binary_search( ) 에도 cmp 사용
3. return 은 true | false로 나옴
   3.1. cout 찍어보면 1 | 0

---

lower_bound / upper_bound

• binary_search를 사용하고 싶은데 idx를 찾고 싶은 경우 사용하자!
  • lower_bound 는 value와 비교해, value <= i
  • upper_bound는 value와 비교해, value < i

#include <iostream>
#include <algorithm>

int main(void){
	lower_bound(begin, end, value);
    lower_bound(begin, end, value, cmp);
    // -> [begin, end)에서 value보다 작지 않는 첫 번째 이터레이터
    
    
    upper_bound(begin, end, value);
    upper_bound(begin, end, value, cmp);
    // -> [begin, end)에서 value보다 큰 첫 번째 이터레이터
    
    
}

---

value값이 있는 경우

---

value값이 없는 경우

---

rotate

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int> arr = {1,2,3,4,5,6,7,8,9,10};

    rotate(arr.begin(),arr.begin()+3,arr.end());

    for(int i=0;i<arr.size();i++){
        cout << arr[i] << ' ';
    }
    cout<<'\n';

    deque<int> dq = {1,2,3,4,5,6,7,8,9,10};
    rotate(dq.begin(),dq.begin()+3,dq.end());
    while(!dq.empty()){
        cout << dq.front() << ' ';
        dq.pop_front();
    }
    cout<<'\n';


    return 0;

}

---

unique

• unique는 구ㄴ에서 연속되는 같은 값을 하나 제외하고 시프트 시킨 후, end() 이터레이터 리턴
  

---

<bitset>

bitset

• bit 용 자료구조

---

10진수 b1=4 -> 2진수 변환

• 

---

10진수 255 -> 2진수 변환

• 

---

2진수 : "1001" 초기값 선언

• 

---

& 연산

• 연산

---

[] 접근

• 

---

set

• b1.set(2) 2번째 필드를 1로 set 시킴
• 

---

reset

• b1.reset(2) 2번째 필드를 0으로 reset 시킴
• 

---

flip

• b1.flip(2) 2번째 필드를 반대로 바꿈
• 

---

string

s.substr(시작, 몇개)

---

공백 split

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main(void){
    string s1="abcde fg hijklmn opkrstu v w xyz";
    deque<string> sp;

    int before_idx = 0;
    for(int i=0; i<s1.length(); i++){
        if(s1[i] == ' ' || i == s1.length()-1){
            sp.push_back(s1.substr(before_idx,i-before_idx));
            before_idx=i+1;
        }
    }

    for(int i=0;i<sp.size();i++){
        cout << sp[i] << '\n';
    }

    return 0;
}