교집합(Intersection) 연산이란?
두 배열 사이의 교집합은 두 배열에 공통으로 존재하는 원소들의 집합을 의미합니다.
예를 들어 다음과 같은 두 배열이 있다고 가정해 보겠습니다.
- 배열 1 = {1, 2, 3, 4, 6}
- 배열 2 = {1, 2, 5, 6, 7}
이때 배열 1과 배열 2의 교집합은 다음과 같습니다.
Array1 ∩ Array2 = {1,2,3,4,6} ∩ {1,2,5,6,7}
= {1,2,6}즉, 두 배열 모두에 포함된 원소 {1, 2, 6}만 결과로 남게 됩니다.
교집합 연산의 기본 논리
교집합을 구하는 핵심 아이디어는 매우 간단합니다. 첫 번째 배열의 각 원소를 두 번째 배열의 모든 원소와 비교하여, 값이 같은 경우 그 원소를 결과 배열에 저장하면 됩니다.
k=0;
for(i=0;i<size1;i++){
for(j=0;j<size2;j++){
if(a[i]==b[j]){
intersection[k]=a[i];
k++;
}
}
}위 코드에서 이중 반복문을 사용해 두 배열의 모든 원소 쌍을 비교하고, 일치하는 값을 intersection 배열에 차례대로 저장합니다.
C 프로그램 전체 코드
다음은 두 배열에 대해 교집합 연산을 수행하는 완전한 C 프로그램입니다. 이 프로그램은 단순히 교집합을 찾는 것뿐만 아니라, 결과 배열을 정렬하고 중복된 원소까지 제거하여 깔끔한 최종 결과를 출력합니다.
#include<stdio.h>
int removerepeated(int size,int a[]);
void sort(int size,int a[]);
main(){
int i,size1,size2,size,j=0,k,intersectionsize;
printf("첫 번째 배열의 크기를 입력하세요\n");
scanf("%d",&size1);
printf("두 번째 배열의 크기를 입력하세요\n");
scanf("%d",&size2);
int a[size1],b[size2],uni[size1+size2];
if(size1<size2){
intersectionsize=size1;
}else if(size1>size2){
intersectionsize=size2;
}else{
intersectionsize=size1;
}
int intersection[intersectionsize];
printf("첫 번째 배열의 원소를 입력하세요\n");
for(i=0;i<size1;i++){
scanf("%d",&a[i]);
}
printf("두 번째 배열의 원소를 입력하세요\n");
for(i=0;i<size2;i++){
scanf("%d",&b[i]);
}
// 교집합 계산 시작
k=0;
for(i=0;i<size1;i++){
for(j=0;j<size2;j++){
if(a[i]==b[j]){
intersection[k]=a[i];
k++;
}
}
}
// 정렬
sort(k,intersection);
// 중복 제거
size=removerepeated(k,intersection);
printf("교집합 결과 배열\n");
if(size>0){
for(i=0;i<size;i++){
printf("%d\n",intersection[i]);
}
}else{
printf("교집합이 없습니다\n");
}
}
int removerepeated(int size,int a[]){
int i,j,k;
for(i=0;i<size;i++){
for(j=i+1;j<size;){
if(a[i]==a[j]){
for(k=j;k<size;k++){
a[k]=a[k+1];
}
size--;
}else{
j++;
}
}
}
return(size);
}
void sort(int size,int a[]){
int i,j,temp;
for(i=0;i<size;i++){
for(j=i+1;j<size;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}프로그램의 주요 구성 요소
- removerepeated(): 교집합 결과에서 중복된 원소를 제거하는 함수입니다. 동일한 값이 여러 번 나타날 경우 뒤쪽 원소들을 앞으로 당겨 하나만 남깁니다.
- sort(): 선택 정렬(selection sort) 방식으로 결과 배열을 오름차순으로 정렬하는 함수입니다.
- 교집합 크기 결정: 교집합은 두 배열 중 더 작은 배열의 크기를 넘을 수 없으므로, 두 크기 중 작은 값만큼 결과 배열을 선언합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Enter size of an array1 5 Enter size of an array2 2 Enter numbers for array 1 4 5 6 7 8 Enter numbers for array 2 4 1 Array after intersection 4
첫 번째 배열 {4, 5, 6, 7, 8}과 두 번째 배열 {4, 1}의 공통 원소는 4 하나뿐이므로, 최종적으로 4만 출력됩니다. 만약 두 배열에 공통 원소가 하나도 없다면 "No intersection(교집합 없음)" 메시지가 출력됩니다.