11-1 (정렬 응용: 집합 다시보기)

집합은 원소의 중복을 허용하지 않으며 원소들 사이에 순서가 없다는 면에서 리스트와는 다름.

추상자료형을 통해 집합의 비교나 합집합, 차집합, 교집합 등을 더욱 효과적으로 구현할 수 있다.

삽입연산: insert

집합에 원소 삽입 시 먼저 중복검사를 진행해야 함.

만약 중복 되었다면 삽입하지 않아야 함.

중복이 아니라면 삽입하는데, 위치를 찾아서 리스트를 정렬된 상태로 찾아야 한다.

리스트의 insert() 연산을 통해 삽입할 수 있고, 리스트의 정렬 유무와 상관 없이 바뀌지 않는다.

비교연산: __eq__

두 집합이 동일한 집합인지 비교할 때 사용됨.

정렬되지 않은 상태에서는 A의 모든 원소가 B에 있는지, 그 반대의 경우까지 검사해야 함.

이 경우 각 집합의 원소의 개수가 모두 n이라고 가정하면, 시간복잡도는 O(n^2)이 된다.

만약 배열이 정렬되었다면 비교 연산은 두 집합의 원소의 개수가 같아야 같은 집합이 될 수 있고,

두 집합이 모두 정렬되어 있으므로 순서대로 같은 원소를 가져야 한다.

( 가장 작은 원소부터 하나씩 끝까지 서로 비교하여 모두 같아야 같은 집합임. )

합집합 연산: union

원소들이 크기순으로 정렬되어 있다면 한 번의 스캔만으로 합집합을 구할 수 있다.

두 집합의 원소들이 크기순으로 정렬되어 있으므로, 가장 작은 원소들부터 비교하여 더 작은 원소를 새로운 집합에 넣고 그 집합의 인덱스를 증가시킨다.

만약 두 집합의 현재 원소가 동일하면 하나만을 새 집합에 넣으면 되고, 인데스는 모두 증가시킨다.

한쪽 집합이 모두 처리되면 나머지 집합의 남은 모든 원소를 순서대로 새 집합에 넣는다.

이 연산은 두 집합의 원소의 개수 합에 비례하는 비교가 필요하므로 만약 두 집합의 크기를 n이라고 한다면, 시간 복잡도는 O(n)이 된다.

* 아래의 표는 리스트로 집합 구현 시 정렬 유무에 따른 복잡도를 비교한 것이다.

" 결론, 정렬을 사용하면 삽입이 번거롭지만 집합의 여러 연산들을 훨씬 효율적으로 처리할 수 있다."

도로로 Dororo