C++ 코딩테스트 강좌, 집합 표현하기

코딩테스트에서 자주 사용되는 집합 표현과 관련된 알고리즘 문제를 다루어 볼 것입니다. 집합을 효과적으로 표현하고 다리기 위해서는 다양한 데이터 구조와 알고리즘의 이해가 필수적입니다. 이번 글에서는 집합을 표현하고, 연산을 수행하는 알고리즘 문제를 하나 제시하고 이를 단계별로 해결해보도록 하겠습니다.

문제: 두 집합의 교집합

주어진 두 수의 집합에서 공통으로 포함된 원소들의 집합을 구하는 문제입니다. 이는 기본적인 집합 연산 중 하나이며, C++ STL을 활용하여 간단히 해결할 수 있습니다.

문제 정의


입력:
 - 두 정수 N, M (1 ≤ N, M ≤ 100,000): 첫 번째 집합의 원소 개수 N, 두 번째 집합의 원소 개수 M
 - 첫 번째 집합의 원소: N개의 정수 a1, a2, ..., aN
 - 두 번째 집합의 원소: M개의 정수 b1, b2, ..., bM

출력:
 - 두 집합의 교집합의 원소를 오름차순으로 출력하라.

예시

문제 풀이 과정

1단계: 문제 분석

주어진 두 집합에서 교집합을 찾기 위해서는 두 집합의 원소를 비교하여 공통으로 존재하는 원소를 찾아야 합니다. 이를 위해 해시셋(집합) 자료구조를 사용할 수 있으며, C++의 STL에서는 std::unordered_set를 제공하므로 이를 활용할 수 있습니다.

2단계: 알고리즘 설계

알고리즘은 다음과 같이 설계할 수 있습니다.

두 집합을 각각 입력받는다.
첫 번째 집합의 원소들을 해시셋에 저장한다.
두 번째 집합의 각 원소를 순회하면서 첫 번째 집합의 해시셋에 존재하는지 확인한다.
존재한다면 교집합 원소 리스트에 추가한다.
결과를 오름차순으로 정렬한 후 출력한다.

3단계: C++ 코드 구현

위의 알고리즘을 바탕으로 C++ 코드를 작성해보겠습니다.


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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    unordered_set setA;
    vector intersection;

    // 첫 번째 집합 입력받기
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        setA.insert(a);
    }

    // 두 번째 집합 입력받기 및 교집합 찾기
    for (int i = 0; i < M; i++) {
        int b;
        cin >> b;
        // setA에 b가 존재하면 intersection에 추가
        if (setA.find(b) != setA.end()) {
            intersection.push_back(b);
        }
    }

    // 교집합 원소 정렬
    sort(intersection.begin(), intersection.end());

    // 결과 출력
    for (int num : intersection) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

4단계: 코드 설명

이 코드에서는 다음과 같은 작업을 수행합니다:

unordered_set setA;: 첫 번째 집합의 원소를 저장하기 위한 unordered_set을 선언합니다.
vector intersection;: 교집합 원소를 저장하기 위한 벡터를 선언합니다.
첫 번째 집합의 원소를 입력받아 setA.insert(a);를 통해 해시셋에 추가합니다.
두 번째 집합의 각 원소를 순회하면서 setA.find(b)를 통해 첫 번째 집합에 존재하는지 확인하고, 존재하면 교집합 배열에 추가합니다.
마지막으로 결과를 정렬하고 출력합니다.

5단계: 복잡도 분석

시간 복잡도 측면에서 봤을 때, 첫 번째 집합의 원소를 해시셋에 추가하는 과정은 O(N)이고, 두 번째 집합의 각 원소에 대해 해시셋을 검색하는 과정은 O(M)입니다. 따라서 전체 알고리즘의 시간 복잡도는 O(N + M)입니다. 메모리 복잡도는 해시셋과 교집합 저장을 위한 메모리 사용을 고려할 때 O(N + min(N, M))입니다.

정리 및 결론

이번 포스팅에서는 집합을 표현하고 교집합을 계산하는 문제를 다루어 보았습니다. C++의 STL을 활용하여 간단히 구현할 수 있었으며, 알고리즘의 시간 복잡도 또한 효율적인 것을 확인할 수 있었습니다. 이러한 방식으로 집합 관련 문제를 효과적으로 해결하기 위해서는 적절한 자료구조를 선택하는 것이 중요합니다.

추가적인 학습을 위해 다양한 연습문제와 함께 집합의 다른 연산들(합집합, 차집합 등)에 대해서도 학습해보시기를 추천드립니다. 감사합니다!