[C++] 중복 처리 (2)

본문

중복 인덱스 처리

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

int main() 
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 generator(seed);

    std::vector<std::pair<std::string, std::string>> word_pairs =
    {
        {"game", "게임"},
        {"start", "시작하다"},
        {"smart", "똑똑한"},
        {"string", "문자열"},
        {"combination", "조합"},
        {"pair", "쌍"}
    };

　다음과 같이 벡터에 단어와 그 정의가 저장되어 있고, 여기서 무작위로 5개의 문제를 낸다고 해보자. 이때 중복된 문제가 없으려면 어떻게 해야 할까? 

 

출처: cppreference

 

　std::shuffle() 함수는 C++11부터 도입되었으며, 주어진 범위의 시퀀스를 무작위로 섞는 함수다. 이때 외부에서 제공하는 난수 생성기, 이를테면 std::19937을 사용하도록 설계되어 있어, 좋은 품질의 난수를 제공한다. 이때 C++ Reference 사이트에서 해당 키워드를 검색하면, std::random_shuffle() 함수에 대한 설명도 같이 제공되는데, 해당 함수는 C++98에 도입되어 C++14에서 폐기되었고, C++17에서 완전히 제거되어 사용하지 않는 것을 강력하게 권하고 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

int main()
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 generator(seed);

    std::vector<std::pair<std::string, std::string>> word_pairs =
    {
        {"game", "게임"},
        {"start", "시작하다"},
        {"smart", "똑똑한"},
        {"string", "문자열"},
        {"combination", "조합"},
        {"pair", "쌍"}
    };
    std::vector<int> indices(word_pairs.size());
    
    for (size_t i = 0; i < word_pairs.size(); ++i) 
        indices[i] = i;
    
    std::shuffle(indices.begin(), indices.end(), generator);

    for (int i = 0; i < 5; ++i) 
        std::cout << word_pairs[indices[i]].first << ": " << word_pairs[indices[i]].second << "\n";

    return 0;
}

출력 결과

 

　인덱스 벡터를 단어 벡터의 개수만큼 생성하고 초기화한다. 그리고 std::shuffle() 함수와 난수 생성기 generator를 이용해 인덱스 벡터를 섞은 후, 원하는 개수만큼의 인덱스를 사용하여 단어 쌍을 출력하면 된다. 해당 알고리즘은 인덱스 벡터를 초기화(O(n))하고, for 루프를 사용하여 인덱스를 초기화(O(n))한 후, std::shuffle() (O(n))하므로, O(n)이다.

---

#include <iostream>
#include <vector>
#include <set>
#include <random>
#include <chrono>

int main() 
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 generator(seed);

    std::vector<std::pair<std::string, std::string>> word_pairs =
    {
        {"game", "게임"},
        {"start", "시작하다"},
        {"smart", "똑똑한"},
        {"string", "문자열"},
        {"combination", "조합"},
        {"pair", "쌍"}
    };
    std::set<int> selected_index;
    
    for(int i = 0; i < 5; ++i)
    {
        std::uniform_int_distribution<int> dist(0, 5);
        int random_index = dist(generator);
        
        while (selected_index.find(random_index) != selected_index.end())
            random_index = dist(generator);
        selected_index.insert(random_index);

        std::cout << word_pairs[random_index].first << ": " << word_pairs[random_index].second << "\n";
    }

    return 0;
}

출력

 

　이번에는 std::set을 사용하여 이미 사용한 인덱스는 제외하고 출력하도록 설계해보았다. 해당 코드는 중복 없이 무작위 인덱스를 생성하는 과정을 좀 더 직관적으로 보여주지만, 추가적인 메모리를 사용하며,중복된 인덱스가 계속 생성될 가능성이 있어 예상치 못한 성능 저하가 발생할 수 있다는 단점이 있다.

---

요약

중복된 인덱스 처리
- 중복된 인덱스를 처리하는 방법으로는 std::set을 사용하여 이미 선택된 인덱스를 제외하는 방법과 std::shuffle()을 이용한 인덱스 벡터 셔플링 방법이 있음. std::set은 추가 메모리를 필요로 하며 예상치 못한 성능 저하의 위험이 있기 때문에 std::shuffle() 사용을 권장.