this.algorithm(2). merge() 함수, copy() max(), min() 함수 ★★★★★

※ 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

11728번: 배열 합치기

 

 

 

 

 

 

 

 

 

 

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

 

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

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

 

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

 

The C++ Programmin Lauguage

 

#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은 없다.)