코딩테스트에서 자주 사용되는 집합 표현과 관련된 알고리즘 문제를 다루어 볼 것입니다. 집합을 효과적으로 표현하고 다리기 위해서는 다양한 데이터 구조와 알고리즘의 이해가 필수적입니다. 이번 글에서는 집합을 표현하고, 연산을 수행하는 알고리즘 문제를 하나 제시하고 이를 단계별로 해결해보도록 하겠습니다.
문제: 두 집합의 교집합
주어진 두 수의 집합에서 공통으로 포함된 원소들의 집합을 구하는 문제입니다. 이는 기본적인 집합 연산 중 하나이며, C++ STL을 활용하여 간단히 해결할 수 있습니다.
문제 정의
입력:
- 두 정수 N, M (1 ≤ N, M ≤ 100,000): 첫 번째 집합의 원소 개수 N, 두 번째 집합의 원소 개수 M
- 첫 번째 집합의 원소: N개의 정수 a1, a2, ..., aN
- 두 번째 집합의 원소: M개의 정수 b1, b2, ..., bM
출력:
- 두 집합의 교집합의 원소를 오름차순으로 출력하라.
예시
입력:
5 4
1 2 3 4 5
3 4 5 6
출력:
3 4 5
문제 풀이 과정
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: 첫 번째 집합의 원소를 저장하기 위한 unordered_set을 선언합니다.setA; vector: 교집합 원소를 저장하기 위한 벡터를 선언합니다.intersection; - 첫 번째 집합의 원소를 입력받아
setA.insert(a);를 통해 해시셋에 추가합니다. - 두 번째 집합의 각 원소를 순회하면서
setA.find(b)를 통해 첫 번째 집합에 존재하는지 확인하고, 존재하면 교집합 배열에 추가합니다. - 마지막으로 결과를 정렬하고 출력합니다.
5단계: 복잡도 분석
시간 복잡도 측면에서 봤을 때, 첫 번째 집합의 원소를 해시셋에 추가하는 과정은 O(N)이고, 두 번째 집합의 각 원소에 대해 해시셋을 검색하는 과정은 O(M)입니다. 따라서 전체 알고리즘의 시간 복잡도는 O(N + M)입니다. 메모리 복잡도는 해시셋과 교집합 저장을 위한 메모리 사용을 고려할 때 O(N + min(N, M))입니다.
정리 및 결론
이번 포스팅에서는 집합을 표현하고 교집합을 계산하는 문제를 다루어 보았습니다. C++의 STL을 활용하여 간단히 구현할 수 있었으며, 알고리즘의 시간 복잡도 또한 효율적인 것을 확인할 수 있었습니다. 이러한 방식으로 집합 관련 문제를 효과적으로 해결하기 위해서는 적절한 자료구조를 선택하는 것이 중요합니다.
추가적인 학습을 위해 다양한 연습문제와 함께 집합의 다른 연산들(합집합, 차집합 등)에 대해서도 학습해보시기를 추천드립니다. 감사합니다!