집합과 프로그래밍
Array 끼리 더하거나 빼게 된다면 합집합, 교집합 등을 구현해 주는것이 일이지만, 집합을 프로그래밍을 통해 구현하려 하다보니 Linq와 관련된 기능을 알게 되었고, 정리하기 위해서 글을 남기게 되었습니다.
이번에 다룰 집합과 관계 있는 Linq 기능은 4가지 입니다.
| 명령어 | 기능 |
| Union | 두 집합을 합치고 중복값을 제거합니다 |
| Intersect | 두 집합의 교집합을 구합니다 |
| Except | 두 집합 사이의 차집합을 구합니다 |
| Distinct | 중복값을 제거합니다. |
합집합 - Union
합집합은 A집합과 B집합의 원소들을 더해 하나의 집합으로 반환 합니다.
벤다이어 그램으로 보면 다음과 같으며, 코드로 나타내면 다음과 같은 Linq식을 사용할 수 있습니다.
Linq를 이용한 코드
int [] A = { 1, 2, 3, 4 };
int [] B = { 1, 3, 4, 5 };
var union = A.Union(B).ToArray();
// union == { 1, 2, 3, 4, 5}위의 예제를 보면 A집합과 B집합의 교집합을 자동적으로 빼주어 합집합을 반환합니다.
또한 다른 방법으로는
A와 B 집합의 모든 값을 더한 다음에 교집합을 빼주는 형태 입니다.
- A와 B집합을 합집합에 더해준다. (이후, 합집합을 정렬해준다)
- 이후 합집합에서 교집합을 빼준다
int[] A = { 1, 2, 3, 4 };
int[] B = { 1, 2, 3, 3, 5 };
var union = new List<int>();
union.AddRange(A);
union.AddRange(B);
union = union.OrderBy(u => u).ToList();
var intersect = A.Intersect(B).ToList();
for (int i = 0; i < intersect.Count; ++i)
{
union.Remove(intersect[i]);
}
교집합 - Intersect
교집합은 간단하게 A와 B집합간의 공통 요소를 반환하는 집합입니다.
Linq를 이용한 코드
int [] A = { 1, 2, 3, 4 };
int [] B = { 1, 2, 3, 5 };
var result = A.intersect(B).ToArray();
// result == { 1, 2, 3 }위처럼 간단하게 Linq 구문을 사용해서 반환할 수 있습니다.
또한 쉽게 Intersect 를 코드로 간단히 구현해 볼 수 있습니다.
Intersect 를 만들기 위해서 는 다음과 같은 절차를 따릅니다.
- 각각 집합에 있는 중복 값을 제거하기 위해 Set으로 중복값을 제거한다
- 두개의 집합에 모두 같은 요소가 있다면 중복값을 체크한다
- 이후 GetMultiplicity 함수를 통해서 각 원소의 중복값이 몇개인지 확인하여, Intersect 집합에 추가해준다.
static void Main(string[] args)
{
int[] A = { 1, 2, 3, 4 };
int[] B = { 1, 2, 3, 3, 5 };
var setA = new HashSet<int>(A);
var setB = new HashSet<int>(B);
var intersect = new List<int>();
foreach(var element in setA)
{
if(setB.Contains(element))
{
int this = GetMultiplicity(A, element);
int other = GetMultiplicity(B, element);
int min = this < other ? this : other;
for (uint i = 0; i < min; ++i)
{
intersect.Add(element);
}
}
}
}
public static int GetMultiplicity(int[] array, int element)
{
return array.Count(s => s == element);
}
차집합 - Except
차집합은 간단하게 A집합에서 B집합을 빼주는 식입니다.
Linq를 이용한 코드
int [] A = { 1, 2, 3, 4 };
int [] B = { 1, 2, 3, 5 };
var result = A.Except(B).ToArray();
// result == { 4 }이런식으로 쉽게 차집합을 알 수 있습니다.
혹은 A집합에서 A와 B의 교집합을 빼는것으로 같은 연산을 할 수 있습니다.
int[] A = { 1, 2, 3, 4 };
int[] B = { 1, 2, 3, 3, 5 };
var result = new List<int>();
result = A.ToList();
var intersect = A.Intersect(B).ToList();
for (int i = 0; i < intersect.Count; ++i)
{
result.Remove(intersect[i]);
}위와 같은 방법으로 구현해 볼 수 있습니다.
중복값 제거 - Distinct
중복값 제거는 매우 간단한 방법입니다.
int[] A = { 1, 2, 2, 3, 4 };
var result = A.Distinct().ToArray();
// result == { 1, 2, 3, 4 }이런식으로 중복값을 제거해 줄 수 있습니다.
추가 - 멱집합 구하기
알다싶이 멱집합은 어떤 집합의 부분집합을 모은 것 입니다.
예를 들자면 아래와 같이 A라는 배열에서 나올 수 있는 멱집합은 다음과 같습니다.
int [] A = { 1, 2 }
//powerSet = { {}, {1}, {2}, {1, 2} }그렇다면 멱집합을 어떻게 하면 쉽게 구할 수 있을까요?
멱집합을 구하기 위해서는 많은 방법이 있지만 StackOverFlow에 나온 방법을 참고하였습니다.
이 방법을 이용하는 원리는 다음과 같습니다.
- 멱집합의 개수는 2 ^ N개
- 2진수로 나타낼 수 있는 수의 개수도 2 ^ N개
그렇다면 어떤식으로 표현을 할 수 있을까요?
int totalCount = 1 << Set.Count();
for (int bitMask = 0; bitMask < totalCount; ++bitMask)
{
for (int j = 0; j < Set.Count(); ++j)
{
if ((bitMask & (1 << j)) > 0)
{
powerSet.Add(Set[j]);
}
}
}위와 같은 코드를 작성하게 되면 아래와 같이 하나씩 원소들이 집합으로 들어가는 것을 알 수 있습니다.
즉, 0 이 꺼진상태 1이 켜진상태로 보았을때 0 과 1 이 꺼지고 켜지면서 모든 원소들이 표현이 됩니다.
0 000 ...
1 001 ..z
2 010 .y.
3 011 .yz
4 100 x..
5 101 x.z
6 110 xy.
7 111 xyz이러한 방법을 이용해서 List 안의 List를 만든다면 모든 부분집합을 가진 멱집합을 구할 수 있습니다.
최근댓글