this.code();

§ my solution 

추출,삽입이 빠른 덱으로 size가 1이 되기 전까지 진행

제일 처음 삭제

dq.erase(dq.begin());

처음값 back으로 push

dq.push_back(dq[0]);

제일 front pop

dq.pop_front();

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

deque<int> dq;

int main(){
    int n;  cin >> n;
    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1){
        dq.erase(dq.begin());
        dq.push_back(dq[0]);
        dq.pop_front();
    }
    cout << dq[0];
}

※ 이번 문제에서 알게된 점

§ insert() 함수

dq.insert함수는 insert(pos, val);로 값이 들어가야 해서 dq.insert(dq.end()+i, dq.begin()+i);처럼 사용하지 말아야 한다.

위와 같은 의미로 다시 코드를 짜고 싶다면 다음과 같이 dq.insert(dq.end()+i, dq[i]); 와 같이 사용해야 한다.

dq.insert(dq.end()+i+1, dq[i]); // 정상적인 작동
dq.insert(dq.end()+i+1, dq.begin(i));  // dq.begin(i) 부분에 오류발생
dq.insert(dq.end()+i+1, dq.begin()+i); // dq.insert() 부분에 오류발생

§ front 와 begin 의 차이

가장 고생했던 부분이 있는데 다음과 같다.

<정답코드>

for (int i = 0; i < k-1; i++) {
    dq.push_back(dq.front());
    dq.pop_front();
}
cout << dq.front() << ", ";
dq.erase(dq.begin());

// 7 3
// <3, 6, 2, 7, 5, 1, 4>

<오답코드>

for (int i = 0; i < k; i++) {
    dq.insert(dq.end()+i+1, dq[i]);
    dq.erase(dq.begin()+i);
}
dq.pop_back();

// 7 3
// <2, 4, 7, 7, 7, 7, 7>

front()는 첫 "요소"를 반환하는 것이다.

begin()은 그 요소의 참조 즉, "주소값"을 반환한다.

즉, begin은 컬렉션을 통해 반복하는 데 사용할 수 있는 해당 요소의 iterators를 반환하지만

      front는 컬렉션의 첫 번째 요소에 대한 참조만 반환 (포인터 개념)합니다.

따라서 push_back(값); 메소드를 활용하기 위해서는 front를 사용하는 것이 좋다.

dq.push_back(dq.front());

§ my solution 

추출,삽입이 빠른 덱으로  k - 1번씩 밀고, 맨 앞에있는 값을 제거하는 알고리즘을, 모든 값이 없어질 때 까지 반복

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

deque<int> dq;
int main(){
    int n, k;   cin >> n >> k;
    cout << '<';


    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1) {
        for (int i = 0; i < k-1; i++) {
            dq.push_back(dq.front());
            dq.pop_front();
        }
        cout << dq.front() << ", ";
        dq.erase(dq.begin());
    }
    cout << dq[0];
    cout << '>';
}

§ 시행착오 

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

deque<int> dq;
int main(){
    int n, k;   cin >> n >> k;
    cout << '<';


    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1) {
            if (dq.size() > 2) {
                cout << dq[k-1] << ", ";
                for (int i = 0; i < k; i++) {
                    dq.insert(dq.end()+i+1, dq[i]);
                    dq.erase(dq.begin()+i);
                }
                dq.pop_back();
            }
            else if(dq.size() <= 2){
                cout << dq[0] << ", "<< dq[1];
                break;
            }
    }
    cout << dq[0];
    cout << '>';
}

왜 이따구로 풀었을까?

- 일단 먼저 다음과 같이 접근하였다.

1 2 3 4
                    7  6  5

             front                  back <-- 삽입
                    1 2 3 4 5 6 7
                    (1 2 3) 4 5 6 7 [1 2 3]
                    4 5 6 7 1 2
                    (4 5 6) 7 1 2 [4 5 6]
                    7 1 2 4 5
                    4 5 7 1
                    1 4 5
                    4 5 1
>> 그대로 출력       5 1 4

왜 안될까?  => k값이 3이라 저렇게 출력되는 것처럼 보일 뿐, 다음과 같은 테스트 케이스에서는 오답으로 나온다.

10 1
<1, 2, 3, 4, 5, 6, 7, 8, 9, 10>

5 5
<5, 1, 3, 4, 2>

10 4
<4, 8, 2, 7, 3, 10, 9, 1, 6, 5>

따라서 예제의 특수성에 빠지지 않도록 조심할 것!

※ 이번 문제에서 알게된 점

if (!s.compare("문자열"))

§ a.compare(b) 함수

C++에서 string 헤더에 제공되는 함수.

a와 b의 문자열이 서로 같다면 return 0
a와 b의 문자열이 서로 다르면 return -1

§ if (!s.compare("문자열")) 

문자열이 같으면 0을 반환하므로 if(0)은 if (false)와 동일하게 취급된다.
따라서 if (!s.compare("문자열")은 if (!0) 즉, if (!false) == if(true)이다.

§ my solution 

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

int main(){
    int n;  cin >> n;
    stack<int> intStack;
    for (int i = 0; i < n; i++) {
        string s;   cin >> s;
        if (!s.compare("push")){
            int push_num;   cin >> push_num;
            intStack.push(push_num);
        }

        else if (!s.compare("pop")){
            if (intStack.empty())
                cout << "-1" << endl;
            else{
                cout << intStack.top() << endl;
                intStack.pop();
            }
        }

        else if (!s.compare("size")){
            cout << intStack.size() << endl;
        }

        else if (!s.compare("empty")){
            if (intStack.empty())
                cout << "1" << endl;
            else
                cout << "0" << endl;
        }

        else if (!s.compare("top")){
            if (intStack.empty())
                cout << "-1" << endl;
            else
                cout << intStack.top() << endl;

        }
    }
}

C++에서 가장 번거로운것 중 하나는 문자열 처리이다.

Tip!

1. getline은 앞뒤 개행문자까지 다 읽어온다.

string str;
getline(cin, str);

2. 문자 "0"를 int로 바꾸려면 '0'을 빼준다.

3. str.find(str2)를 했는데 못찾을 때, -1을 반환한다 생각해도 된다! (사실은 string::npos를 반환하지만)

4. str.find(str2, index)는 index 부터 탐색한다.

5. str.erase(index, size)는 삭제를 시작할 index와 크기이다.

※ 문자열 자르기

Case 1) string 클래스 사용할 때

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

int main() {
    string str = "Hello, world, Korea";
    size_t prev = 0;
    size_t curr = str.find(','); //못찾으면 npos 반환
    
    while (curr != string::npos) {
        string substring = str.substr(prev, curr - prev);
        cout << substring << ' ';
        prev = curr + 1;
        curr = str.find(',', prev);
    }
    cout << str.substr(prev, curr - prev);
}

Case 2) sstream 클래스 이용할 때

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

int main() {
    string str = "Hello world and Korea";
    istringstream iss(str);
    string token;
    
    while (getline(iss, token, " ")){
        cout << token << endl;
    }
}

Case 3) 특정 문자열 찾기

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

int main() {
    string str = "hello my name is V2LLAIN";
    string word = "V2";

    int pos = str.find(word);

    while (pos != string::npos) {
        cout << str.substr(pos, word.size()) << endl;
        pos = str.find(word, pos+word.size());
    }
}

출처: https://velog.io/@siyeonkm/cpp-%EC%BD%94%ED%85%8C%EC%97%90%EC%84%9C-%EC%95%8C%EC%95%84%EC%95%BC%ED%95%98%EB%8A%94%EA%B2%83%EB%93%A4

※ 가장 많이 출제되는 코딩테스트 유형들

1. DFS / BFS

2. 문자열

3. 구현

4. DP

https://velog.io/@pppp0722/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%EC%9C%A0%ED%98%95-%EC%A0%95%EB%A6%AC

vector / pair / stack ,queue, deque, priority queue / map / set  / algorithm / iterator / bitset

※ vector(std::vector) _가변배열 / 가장 기본이 되는 컨테이너 (★★★★★)

#include <vector>
using namespace std;

vector<자료형> 변수명(숫자)    //숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명(숫자, 변수1);   //숫자만큼 벡터 생성 후 변수1으로 모든 원소 초기화
vector<자료형> 변수명{숫자, 변수1, 변수2, 변수3, ...};    // 벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[]={ {변수1, 변수2}, {변수3, 변수4}, ...}   //2차원 벡터생성 (열은 고정, 행 가변)
vector<vector <자료형>> 변수명   //2차원 벡터생성 (열, 행 가변)

ex);
vector<int> vec1; // 크기가 0인 벡터 선언
vector<int> vec2(10); // 크기가 10인 벡터 선언
vector<int> vec3(10, 3); // 크기가 10이고 모든 원소가 3으로 초기화된 벡터
vector<int> vec4 = { 1,2,3,4,5 }; // 크기가 지정한 초기값으로 이루어진 벡터
vector<int> vec5[] = { {1,2},{3,4} }; // 벡터 배열 생성(행은 가변인지만, 열은 고정)
vector<vector<int>> vec6; // 2차원 벡터 생성(행과 열 모두 가변)

※ vector 요소 삽입, 제거, 변경

#include <vector>
using namespace std;

int main() {
    vector<int> vec; // 크기가 0인 벡터 선언

    vec.push_back(10);
    vec.push_back(20); // vec = {10, 20}

    vec.insert(vec.begin() + 1, 100);  // vec = {10, 100, 20}

    vec.pop_back();       // vec = {10,100}

    vec.emplace_back(1);   // vec = {10, 100, 1}
    vec.emplace_back(2);   // vec = {10, 100, 1, 2}
    vec.emplace(vec.begin() + 2, -50); // vec = {10, 100, -50, 1, 2}

    vec.erase(vec.begin() + 1);    // vec = {1, -50, 1, 2}
    vec.resize(6); // vec = {1, -50, 1, 2, 0, 0}
    vec.clear();   // vec = empty()
}

※ vector의 index 접근

※ vec.at(i)와 vec.[i]의 차이점

- at은 범위를 검사하여 범위 밖의 요소에 접근 시 예외처리를 발생시킨다. (std::out_of_range)

- [ ]은 범위검사를 하지 않으며 예외처리를 발생시키지 않는다. (범위 밖 요소에 접근하면 디버깅 발생)

vector는 효율에 중점을 두기에 보통 [ ]를 권장한다.

※ vector의 크기 size, capacity

- size: vector의 크기, 즉 벡터에 실제로 저장된 원소의 개수를 뜻한다.

- capacity: vector의 용량, 즉 벡터의 최대 할당 크기를 뜻한다.

만약 벡터의 크기가 용량을 초과한다면 재할당이 발생한다. (기존 값 새 메모리에 복사 후 파괴)

if (size > capacity) {
    reallocate <- 모든 값 새 메모리에 복사 후 기존 벡터 파괴
}

Problem 1. 새 메모리의 복사과정에서 복사생성자가 발생해 성능이 저하될 수 있다.

Solution 1. reserve()라는 함수를 사용해서 벡터의 용량을 충분히 크게 생성할 수 있다.

Problem 2. reserve()를 너무 크게 잡으면 벡터가 불필요하게 늘어나 메모리를 많이 차지할 수 있다.

Solution 2. clear()로 벡터의 값을 지울 때, 벡터의 요소를 삭제할 수 있다.

Problem 3. clear()로 벡터의 요소는 없어지지만 capacity는 그대로 남아있다.

Solution 3. 이를 해결하기 위해 swap()을 사용하는데 이는 아래와 같다.

#include <vector>
using namespace std;

int main() {
    vector<int> vec = { 1,2,3,4,5 };
    vec.clear();
    cout << vec.capacity() << endl;  // 5 출력
    vector<int>().swap(vec);
    cout << vec.capacity() << endl;  // 0 출력
}

https://chan4im.tistory.com/19?category=1076581 

★★★★★ vector에 값 입력받기  (cin >> vec[i]는 안된다??) ★★★★★

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;

int main() {
    int num;
    for (int i = 0; i < 5; i++){
        //cin >> v[i];  // Err!
        cin >> num;
        v.push_back(num);
    }
    vector<int>::iterator it;
    sort(v.begin(), v.end(), greater<int>());

    for (it = v.begin(); it != v.end(); it++){
        cout << *it << ' ';
    }
}

※ pair

★★★개인적으로 굉장히 유용하다고 생각되는 라이브러리★★★

feat. vector, sort

• 두 자료형을 하나의 쌍(pair)으로 묶는다.
• 첫번째 데이터는 first, 두번째 데이터는 second로 접근, make_pair(val1, val2)로 pair를 생성해준다.
• vector, algorithm 의 헤더파일에 include 하고 있기에 별도의 헤더를 include할 필요가 없다.

#include <iostream>
using namespace std;

#include <vector>

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력
}

pair로  vector, typedef, sort  다루기

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

using namespace std;

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력

    //vector와 pair
    vector<pair<int, int>> v;
    v.push_back(make_pair(10, 20));
    v.push_back(make_pair(30, 40));
    v.push_back(make_pair(50, 60));
    cout << v[0].first << ' ' << v[2].second << endl;

    // typedef를 이용한 방식
    typedef pair<int, int> P;
    vector<P> v1;
    v1.push_back(make_pair(300, 500));
    v1.push_back(make_pair(600, 400));
    v1.push_back(make_pair(100, 200));

    // first 따로, second 따로 정렬
    sort(v1.begin(), v1.end());
    vector<P>::iterator it;

    for (int i = 0; i < 3; i++)
        cout << v1[i].first << " " << v1[i].second << endl;
}

※ stack

#include <stack>

stack<데이터타입> 이름;

https://chan4im.tistory.com/22?category=1076581 

※ stack, queue, deque priority queue, priority queue

※ queue 선언방식

#include <queue>

queue<데이터타입> 이름;

※ deque 선언방식

#include <deque>

deque<데이터타입> 이름;

https://chan4im.tistory.com/29?category=1076581 

※ priority queue 선언방식

#include <queue>

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > pq;
priority_queue<int, vector<int>, less<int> > pq;

가장 기본적인 것 부터 시작해 여러 방식으로 변형하며 사용할 수 있다.

※ map

map은 각 node가 [key - value] 의 쌍(pair)으로 이루어진 트리이다. 

특히나 map의 가장 큰 특징은 중복을 허용하지 않는다는 것이다! => key가 중복되면 insert가 수행되지 않음

C++의 map 내부구현은 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 레드블랙트리로 구성되어 있다.

unordered_map은 해시 테이블이다.

※ map 선언방식 (삭제)

#include <map>

map<key_type, value_type> 이름;

※ map 삭제

※ map에서 찾고자 하는 데이터 확인 (search, find)

map에서 원하는 값을 찾고자 할 때, iterator를 사용한다.

만약 끝까지 원하는 값을 찾지 못하면, iterator는 map.end()를 반환한다.

find(k) 로 사용하며 key값 k에 해당하는 iterator를 반환한다.

map<string, int> mapset;

if (mapset.find("V2LLAIN") != mapset.end()){
    cout << "find!" << endl;
}
else
    cout << "not find!" << endl;

※ 반복문 데이터 접근 (first, second)

※ index 기반 iterator 활용 예제

map<string, int> mapset;

for (auto it = mapset.begin(); it != mapset.end(); it++) {
    cout << it->first << " " << it->second << endl;
}
cout << endl;

※ 범위기반 반복문 활용 예제

map<string, int> mapset;

for (auto it : mapset){
    cout << it.first << " " << it.second << endl;
}

※  map 사용 예제 (insert, search, iterator 구현)

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

map<string, int> mapset;

int main() {

    mapset.insert({ "Alice", 100 });
    mapset.insert({ "Bob", 200 });

    if (mapset.find("Alice") != mapset.end())
    {
        cout << "find" << endl;
    }
    else {
        cout << "not find" << endl;
    }

    //인덱스기반
    for (auto iter = mapset.begin() ; iter !=  mapset.end(); iter++)
    {
        cout << iter->first << " " << iter->second << endl;
    }
    cout << endl;

    //범위기반
    for (auto iter : mapset) {
        cout << iter.first << " " << iter.second << endl;
    }
}

참고) https://life-with-coding.tistory.com/305?category=808106

※ set

- set은 연관 컨테이너로 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 Binary Search Tree로 구현되어 있다.

- key라는 원소들의 "집합"으로 key값은 중복되지 않는다!

- insert()를 통한  자동적으로 오름차순 정렬이 가능하다.

∴ 중복을 피하면서 정렬까지 사용할 때 매우 유용하다!

insert(k) : 원소 k 삽입
begin() : 맨 첫번째 원소를 가리키는 iterator를 반환
end() : 맨 마지막 원소를 가리키는 iterator를 반환
find(k) : 원소 k를 가리키는 iterator를 반환
size() : set의 원소 수
empty() : 비어있는지 확인

※ algorithm

※ STL 알고리즘의 분류

find()는 2개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환 

for_each()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환 

copy()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사

swap()은 2개의 참조가 가리키는 위치의 값을 서로 교환

transform()은 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입후, 출력 반복자가 가리키는 위치에 복사

sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 오름차순정렬.

stable_sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 값이 같은 요소들의 상대적인 순서는 유지,  오름차순으로 정렬합니다.

binary_sort()는 정렬되어있는 경우(오름차순)에 한해서 탐색효율이 매우 좋고 적은 시간에 소요된다.

accumulate()는 두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환합니다.

※ 벡터의 오름차순과 내림차순 정렬 (feat. greater<int> 키워드)

§ sort() 함수 형식

단, custom_func()은 0 또는 1이 나오도록 해야해서 보통 bool형 함수를 많이 넣는다.

sort(v.begin(), v.end()); //형식이나
sort(v.begin(), v.end(), custom_func); //형식으로 사용가능하다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    vector<int> v;
    for (int i = 0; i < 5; i++) {
        int num; cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());   // 오름차순
    sort(v.rbegin(), v.rend()); // 내림차순

    for (auto x: v) {
        cout << x;
    }
}

※ 벡터의 이진탐색 

※ iterator

STL에 저장된 요소를 반복적으로 순회해여 각각의 요소에 대한 접근을 제공하는 객체.

즉, 컨테이너의 구조,요소의 타입과 상관없이 컨테이너에 "저장된 요소"를 순회하는 과정을 일반화한 표현

[iterator를 쓰기 위한 요건]

1. 가리키는 요소의 값에 접근할 수 있어야 한다. => 참조 연산자(*)가 정의되어야 합니다.

2. 반복자 사이의 대입 연산, 비교 연산이 가능해야 합니다. => 대입, 관계 연산자가 정의되어야 합니다.

3. 가리키는 요소의 주변 요소로 이동할 수 있어야 합니다. => 증가 연산자(++)가 정의되어야 합니다.

int main() {
    vector<int> v(5);

    v.push_back(20);
    v.push_back(50);
    v.push_back(10);

    for (int i = 0; i < 5; i++)
        cin >> v[i];

    vector<int>::iterator it;
    for (it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    
    //1 2 3 4 5 20 50 10 출력
}

※ bitset

비트연산의 간편화를 위해 사용하는 라이브러리

#include <bitset>

int main() {
    bitset<100000> a(76),b(44); // 각각 76, 44의 비트가 입력됨
    cout << (a & b) << '\n';
    cout << (a | b) << '\n';
    cout << (a ^ b) << '\n';
    cout << (~a) << '\n';
    cout << (~b) << '\n';
    return 0;
}