this.code();

※ vector를 이용한 합병정렬 구현

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

int main() {
    vector<int> v1(2);
    vector<int> v2(3);

    for (int i = 0; i < v1.size(); i++){
        cin >> v1[i];
    }
    for (int i = 0; i < v2.size(); i++){
        cin >> v2[i];
    }

    vector<int> v3;

    v3.reserve(v1.size() + v2.size());
    v3.insert(v3.end(), v1.begin(), v1.end());
    v3.insert(v3.end(), v2.begin(), v2.end());

    sort(v3.begin(), v3.end());

    for (const auto& x:v3) {
        cout << x << " ";
    }
}

v3.reserve(v1.size() + v2.size());
v3.insert(v3.end(), v1.begin(), v1.end());
v3.insert(v3.end(), v2.begin(), v2.end());

v3.resize(v1.size() + v2.size());
v3.insert(v3.end(), v1.begin(), v1.end());
v3.insert(v3.end(), v2.begin(), v2.end());

위와 아래의 차이점은 뭘까?

즉, reserve와 resize의 차이점은 무엇일까?

§ reserve() 와 resize() 의 차이

capacity: 미리 할당해놓은 배열공간

size: 배열에 들어있는 원소의 수

대부분의 컨테이너 STL 자료구조들은 일정 크기를 할당(capacity)한 후 

size가 capacity를 넘으면 2배정도의 크기를 늘려 이동하는 방식으로 구현되어 있다.

§ reserve(N)

- vector의 capacity를 N으로 설정하는 것.

- N이 현재 capacity보다 클 때만 작동, 작으면 아무 일도 발생X

- N이 현재 capacity보다 크다면 모든 원소 reference와 iterator가 전부 무효화(invalidate)된다.

§ resize(N)   /   resize(N, value)

- size > N인 경우, 원소의 개수를 줄인다.

- size < N인 경우, 입력된 value가 없으면 default값인 0으로 할당한다. 있다면 value로 할당.

  그 후, size가 N이 되도록 늘린다.

※ merge()와 sort()를 이용한 합병정렬 구현

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

int main() {
    vector<int> v1;
    vector<int> v2;

    for (int i = 0; i < 3; i++) {
        int num;    cin >> num;
        v1.push_back(num);
    }
    for (int i = 0; i < 3; i++) {
        int num;    cin >> num;
        v2.push_back(num);
    }
    vector<int> v3;

    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));

    sort(v3.begin(), v3.end());

    for (const auto& x:v3) {
        cout << x << " ";
    }
}

§ merge() 함수의 원리

merge( first1, last1, first2, last2, result );

result = first1 [first2, last2] last1 형식으로 결과값이 result에 누적된다. 

예를 들어 다음과 같은 입력이 주어질 때, 다음과 같이 merge된다.

[v1]: 1 200 3 2
[v2]: 45 5 2 23 31
[v3]: 1 45 5 2 23 31 200 3 2

즉, 아래와 같이 내부적으로 되어있다는 것을 알 수 있다.

[v1]: 1 200 3 2
[v2]: [45 5 2 23 31]
[v3]: 1 [45 5 2 23 31] 200 3 2

§ back_inserter() 함수의 원리와 copy() 함수

벡터의 맨 끝에 값을 삽입하는 "iterator"의 일종이다.

예를 들어 다음과 같이 작동한다.

std::vector<int> v1, v2;
// v1 : 1, 3, 5 , v2 : 10, 30, 50

std::copy(v1.begin(), v1.end(), back_inserter(v2));
v2 : 10, 30, 50, 1, 3, 5 //v2의 맨 끝부터 차례대로 v1의 값들이 복사되어 삽입 된다.

std::copy(v1.begin(), v1.end(), front_inserter(v2));
v2 : 5, 3, 1, 10, 30, 50 //v2의 맨 앞으로 v1의 값들이 복사되어 삽입 된다.

https://www.acmicpc.net/problem/11728

※ max(), min() 2개를 이용한 방법

최대 최소는 값 비교를 해 결정하는 것이다.

이런 값 비교는 많은 상황에서 쓸모가 있다.

따라서 우리는 이에 대해 가장 대표적인 예제로 vector와 pair로 구현해볼 것이다.

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

vector<int> v(5);

int main() {
    int num;
    for (auto x:v) {
        cin >> num;
        v.push_back(num);
    }
    int M = 0;
    int m = 1000000000;
    for (int i = 0; i < v.size(); i++) {
        M = max(v[i], M);
        m = min(v[i], m);
    }
    cout << "최댓값: " << M << "최솟값: " << m;
}

여기서 가장 핵심이 되는 키워드는 for문 안에 있는 max, min 함수이다.

M = max(v[i], M);
m = min(v[i], m);

사실 우리는 이 구문에 대해 많이 봐왔는데 if문으로 표현할 수 있다.

if(M < v[i]){
    M = v[i];
}
if(m > v[i]){
    m = v[i];
}

※ minmax_element() 함수를 이용한 방법

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

vector<int> v;

int main() {
    int num;
    for (int i = 0; i < 5; i++) {
        cin >> num;
        v.push_back(num);
    }

    auto it = minmax_element(v.begin(), v.end());
    cout << "최솟값: " << *it.first << " " << "최댓값" << *it.second << endl;
}

코드의 엄청난 압축이 가능하니 되도록 max, min, minmax함수를 써보는 것을 추천한다.

(cf. maxmin은 없다.)

§ my solution 

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

제일 처음 삭제

dq.erase(dq.begin());

처음값 back으로 push

dq.push_back(dq.front());

제일 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) {
        cout << dq.front() << " ";
        dq.erase(dq.begin());
        dq.push_back(dq.front());
        dq.pop_front();
    }
    cout << dq[0];
}

§ 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];
}

다음 Java 로직을 C++로 구현해 보자.

[Java]

// strategy.java
public interface Strategy {
        public int doOperation(int num1, int num2);
}

// OperationAdd.java
public class OperationAdd implements Strategy{
@Override
    public int doOperation(int num1, int num2) {
        return num1 + num2;
    }
}
// OperationSubstract.java
public class OperationSubstract implements Strategy{
    @Override
    public int doOperation(int num1, int num2) {
        return num1 - num2;
    }
}
// OperationMultiply.java
public class OperationMultiply implements Strategy{
@Override
    public int doOperation(int num1, int num2) {
        return num1 * num2;
    }
}
// Context.java
public class Context {
    private Strategy strategy;
    public Context(Strategy strategy){
            this.strategy = strategy;
        }
    public int executeStrategy(int num1, int num2){
            return strategy.doOperation(num1, num2);
        }
}
// StrategyPatternDemo.java
public class StrategyPatternDemo {
    public static void main(String[] args) {
            Context context = new Context(new OperationAdd());
            System.out.println("10 + 5 = " + context.executeStrategy(10, 5));
            context = new Context(new OperationSubstract());
            System.out.println("10 - 5 = " + context.executeStrategy(10, 5));
            context = new Context(new OperationMultiply());
            System.out.println("10 * 5 = " + context.executeStrategy(10, 5));
        }
}

[C++]

#include <iostream>
using namespace std;

class Strategy{
public:
    virtual int doOperation (int num1, int num2) = 0;
};

class OperationAdd : public Strategy{
public:
    int doOperation(int num1, int num2) override{
        return num1 + num2;
    }
};
class OperationSubstract : public Strategy{
public:
    int doOperation(int num1, int num2) override{
        return num1 - num2;
    }
};
class OperationMultiply : public Strategy{
public:
    int doOperation(int num1, int num2) override{
        return num1 * num2;
    }
};

class Context {
private:
    Strategy *strategy;
public:
    Context(Strategy *strategy){ this->strategy = strategy; }
    int executeStrategy(int num1, int num2) { return strategy->doOperation(num1, num2); }
};

int main(){
    Context *context = new Context(new OperationAdd);
    cout << "10 + 5 = " << context->executeStrategy(10, 5) << endl;

    context = new Context(new OperationSubstract());
    cout << "10 - 5 = " << context->executeStrategy(10, 5) << endl;

    context = new Context(new OperationMultiply());
    cout << "10 * 5 = " << context->executeStrategy(10, 5) << endl;
}

핵심 포인트!

1. private에 Strategy 클래스의 객체를 생성할 수 있다.

2. 생성자의 매개변수로 객체를 생성할 수 있다.

class Context {
private:
    Strategy *strategy;
public:
    Context(Strategy *strategy){ this->strategy = strategy; }
    int executeStrategy(int num1, int num2) { return strategy->doOperation(num1, num2); }
};

※ 이번 문제에서 알게된 점

§ 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;

        }
    }
}

§ [2.6 조언] _  어떻게 C++로 멋진 프로그램을 짤 수 있을까?

- 가능한 경우, 정적으로 타입체크되도록 한다.

- 정보는 지역적으로 보관한다. (전역변수와 포인터의 사용을 최소화)

- 지나치게 추상화하지 않는다.

- C++의 세부사항까지 전부 알 필요는 없다.

§ [3.5 조언] _ 추상화 메커니즘

- 무방비의 new와 delete연산은 피한다.

- 인터페이스와 구현의 완벽한 분리가 필요하다면, 추상클래스를 인터페이스로 활용한다.

- 클래스 계층구조 설계시, 구현상속과 인터페이스 상속을 구분한다.

- 객체의 복사, 이동, 소멸을 통제해야 한다.

- 컨테이너는 값으로 반환한다. (효율성이 중요하다면, move를 이용)

- 함수 템플릿으로 일반적인 알고리즘을 표현한다.

- 람다를 비롯한 함수객체를 이용해 정책과 작동을 표현한다.

- 타입, 템플릿 별칭을 이용해 유사한 기능은 동일한 이름을 부여한다.

§ [4.6 조언] _ 컨테이너와 알고리즘

- 선택가능하다면, 다른 라이브러리보다는 표준라이브러리(std namespace에 정의된)를 우선사용한다.

- 표준라이브러리가 만능이라 생각하지 말자.

- C 스타일 문자열(char*) 보다는 string을 우선사용한다.

- arr[T] 보다는 vector<T>, map<K,V>, unordered_map를 우선 사용한다.

- vector를 기본 컨테이너로 활용한다.

- push_back()  ||  back_inserter 를 통해 컨테이너에 원소를 추가한다.

- 배열에 realloc을 사용하지 않고, vector에 push_back()을 사용한다.

- 일반적인 예외는 main()문에서 잡는다(catch).

- 표준 알고리즘에 대해 직접 만들기 보단 표준알고리즘을 우선사용한다.

- 반복자가 장황해지면 컨테이너 알고리즘을 정의한다.

- 완전한 컨테이너는 범위기반 for문을 사용한다.

§ [5.7 조언] _ 병행성과 유틸리티

- unique_ptr을 이용해 다형성타입 객체를 참조한다.

- shared_ptr을 이용해 공유객체를 참조한다.

- 공유데이터의 사용은 최소화한다.

- 심사숙고없이 효율성이라는 이유만으로 통신을 위해 공유데이터를 선택하지 말 것.

- 간단한 패턴매칭을 위해서는 정규표현식을 사용한다.

- 수치타입의 속성은 numeric_limits로 접근할 수 있다.

- 수치계산처리를 시도할 때는 라이브러리를 활용하자.

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

Week 9.

Week 10.

Week 11.

Week 12.

Week 13.

Week 1.

Week 2.

Week 3.

Week 4.

Week 5.

Week 6.

Week 7-8.