코테 연습할때마다 잊을만 하면 나오는 다중집합이다. 굳이 몰라도 되지만, 모른채 쓰려면 머지소트를 구현해야 하는 굉장한 번거로움이 있기때문에 알아두는게 좋을 것 같아서 포스팅 한다.
1. 다중 집합이란?
기존에 파이썬에서 집합은 보통 set으로 사용한다. 그리고, set의 특징은 중복된 원소를 허용하지 않는다는 점이 있다.
하지만, 중복된 원소를 포함하기 위해 사용되는 개념이 다중집합이고 개념만 다중집합이며 실제로는 리스트에 담아서 나타낸다.
a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]
일반 집합의 합집합: [1,2,3,4,5,6]
일반 집합의 교집합: [1,2,3,4]
다중 집합의 합집합: [1,1,2,2,3,4,5,6]
다중 집합의 교집합: [1,2,3,4]이렇게 된다. 나는 처음에 다중 집합의 합집합, 교집합이 매우 헷갈렸다. a에는 1이 1개고, b에는 1이 2개이니 합집합에는 총 3개가 되는 것이 아닌가 했다.
여기서 우리가 알고있던 집합 개념을 떠올려야 한다.
a 집합을 연두색, b 집합을 하늘색으로 표현한다면 다음과 같다. 그리고 두 집합의 교집합을 포함해 다시 그림을 그리면 다음과 같다.
이렇게 해야 a는 연두색 + 교집합 을 합했을때, 기존의 a 와 동일한 집합이 되고, b는 하늘색 + 교집합을 합했을때, 기존의 b와 동일한 집합이된다.
즉, 겹치는 개수 만큼만 교집합으로 제외 시키고 그 교집합과 나머지를 모두 합한 것이 합집합이기 때문에 앞에서 의문을 가졌던 합집합의 개수가 늘어나지 않는다는 것을 알 수 있다.
2. 다중 집합의 합집합
별거 아닌 짧은 코드 이지만, 완벽하게 이해하는 데에 한참 걸렸다. 생각보다 어려웠던 개념
a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]
a_temp = a.copy()
a_result = a.copy()
for i in b:
if i not in a_temp:
a_result.append(i)
else:
a_temp.remove(i)
# 결과
a_temp코드만 봐서는 정확히 이해가 안될 수도 있다.
일단 a를 2번 복사한 이유부터 알아야 한다. 우리가 보통 합집합을 구할 때에는 A+B-A교B 이다. 여기서 A와 B의 교집합을 차감하는 이유는 무엇일까? 이미 2번이 더해져있기 때문이다. A에는 A교B가 포함되어있고 B에도 A교B가 포함되어있다. 그래서 1번을 차감해줘야 한다.
위의 식에서 a_temp는 a와 b의 교집합을 제거해주기 위한 용도로 사용된다. else이하의 구문에서 a_temp와 b의 교집합을 제거해준 나머지 요소는 b와 a의 차집합이 되는 것이고, b와 a의 차집합과 a를 더하면 합집합이 완성되기 때문에 a_result에 더해주는 것이다.
(A_temp와 B를 비교해서 중복되는 원소를 제거해준다. (=교집합을 미리 제거해준다.) 교집합이 제거된 A_temp는 B와 A의 차집합과 같음으로, A에 이를 더해준다.)
그래서 2개를 따로 따로 복사해야 한다. 그리고 반드시 따로 복사해야 한다. 이 부분은 얕은복사, 깊은복사의 개념인데 관련된 내용을 포스팅 해뒀기 때문에 필요한 사람은 확인하기 바란다.
3. 다중집합의 교집합
교집합은 합집합의 개념에 비해 상대적으로 쉽다. 그냥 A와 B를 비교해 중복되는 원소가 있으면 제거해주고, 제거한 원소를 다른 배열에 담아주면 된다.
a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]
result = []
for i in b:
if i in a:
a.remove(i)
result.append(i)
print(result)