[C++] merge 함수

C++에서 std::merge 함수는 두 개의 정렬된 데이터를 하나로 병합하여 새로운 정렬된 범위를 생성하는 데 사용됩니다. 이는 정렬된 배열이나 컨테이너를 결합하거나 병합 정렬 알고리즘에서 핵심적으로 활용됩니다.

 

1. std::merge 함수란?

동작 원리

std::merge는 두 개의 정렬된 범위를 입력으로 받아 하나의 정렬된 범위로 병합합니다. 이때, 입력 범위가 반드시 오름차순 또는 내림차순으로 정렬되어 있어야 하며, 결과는 새로운 컨테이너나 범위에 저장됩니다.

사용 프로토타입

#include <algorithm>

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);

매개변수

• first1, last1: 첫 번째 입력 범위의 시작과 끝 이터레이터
• first2, last2: 두 번째 입력 범위의 시작과 끝 이터레이터
• result: 병합된 결과를 저장할 출력 범위의 시작 이터레이터

특징

1. 중복 허용: 입력 범위에 동일한 값이 있을 경우, 모두 결과에 포함됩니다.
2. 시간 복잡도: 두 입력 범위의 크기를 각각 n, m이라 할 때, 병합은 O(n + m) 시간 복잡도로 수행됩니다.

2. std::merge 기본 사용법

예제 1: 두 정렬된 벡터 병합

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

int main() {
    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    std::cout << "병합 결과: ";
    for (int val : result) {
        std::cout << val << " ";
    }

    return 0;
}

 

출력 결과

병합 결과: 1 2 3 4 5 6 7 8

예제 2: 내림차순 병합

std::merge는 기본적으로 오름차순으로 병합하지만, 사용자 정의 비교 함수를 전달하면 내림차순으로 병합할 수도 있습니다.

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

int main() {
    std::vector<int> vec1 = {7, 5, 3, 1};
    std::vector<int> vec2 = {8, 6, 4, 2};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin(), std::greater<int>());

    std::cout << "내림차순 병합 결과: ";
    for (int val : result) {
        std::cout << val << " ";
    }

    return 0;
}

 

출력 결과

내림차순 병합 결과: 8 7 6 5 4 3 2 1

예제 3: 중복 제거 병합

병합한 결과에서 중복된 값을 제거하려면 std::unique를 추가로 사용할 수 있습니다.

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

int main() {
    std::vector<int> vec1 = {1, 2, 2, 3};
    std::vector<int> vec2 = {2, 3, 4, 5};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    auto endIt = std::unique(result.begin(), result.end());

    std::cout << "병합 후 중복 제거 결과: ";
    for (auto it = result.begin(); it != endIt; ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

 

출력 결과

병합 후 중복 제거 결과: 1 2 3 4 5

3. 사용 시 주의사항

1. 입력 범위는 정렬되어 있어야 합니다.
   두 입력 범위가 정렬되지 않은 경우, 병합 결과도 정렬되지 않을 수 있습니다.
2. 충분한 크기의 출력 범위 필요
   출력 범위가 두 입력 범위의 크기를 합친 만큼 확보되지 않으면 런타임 에러가 발생할 수 있습니다.
3. 중복 처리 필요
   중복된 값을 제거하려면 std::unique를 추가로 사용해야 합니다.

4. 활용 사례

4.1 병합 정렬

병합 정렬(merge sort) 알고리즘에서 두 정렬된 하위 배열을 병합하는 데 사용됩니다.

4.2 정렬된 데이터 통합

정렬된 파일이나 데이터베이스의 데이터를 통합할 때 유용합니다.

4.3 실시간 데이터 스트림 병합

두 개의 정렬된 데이터 스트림을 실시간으로 처리하고 병합하는 데 사용됩니다.

 

5. 요약

std::merge는 정렬된 데이터를 효율적으로 병합할 수 있는 C++의 강력한 함수입니다. 오름차순, 내림차순 병합부터 중복 제거까지 다양한 활용이 가능하며, 성능도 뛰어납니다. 하지만 입력 데이터의 정렬 상태를 반드시 유지해야 하며, 출력 범위의 크기를 신경 써야 한다는 점을 유의해야 합니다.