[DataScience Computing] Set ADT

1️⃣ SET(셋)

자료구조에서 셋(set)이란 유일한 요소들로만 구성된 컬렉션이다. 즉, 셋 안에는 중복된 요소가 존재할 수 없으며, 각 요소는 한 번만 나타난다. 이 특징 때문에 셋은 주로 요소의 존재 여부를 빠르게 테스트하거나 중복을 제거할 때 사용된다.

 

 

 

 

2️⃣ SET ADT(Abstract Data Type)

✔ 1. Data

• 동일한 유형의 고유 요소 모음이다. 요소는 비교 가능해야 하지만 순서는 중요하지 않다.

✔ 2. Operations

• set(): 새로운 빈 셋을 생성한다.
• size(): 셋의 요소 수를 반환한다.
• contains(e): 셋에 요소 e가 포함되어 있는지 확인하고 Boolean 값을 확인한다.
• insert(e): 셋에 새 요소 e를 삽입한다. e가 이미 존재하는 경우 삽입하지 마라.
• delete(e): 셋에서 요소 e를 제거하고 이를 반환한다.
• equals(setB): 셋이 setB와 같은지 확인한다.
• union(setB): 셋과 seB의 합집합인 새로운 셋을 생성하고 반환한다.
• intersect(setB): 셋과 seB의 교집합인 새로운 셋을 생성하고 반환한다.
• difference(setB): 셋과 seB의 차집합인 새로운 셋을 생성하고 반환한다.
• display(): 화면에 셋을 출력한다.

 

 

3️⃣ SET Implementation(셋의 구현 in Python)

• Set은 다양한 방식으로 구현될 수 있다. 리스트, 트리, 해시구조 등으로 구현 가능하다.
• 예제에서는 리스트를 통해 셋을 구현하도록 하겠으며, Class 형식으로 구현하겠다.

class Set:				#집합 클래스
	def __init__(self):		#생성자
    	self.items = []			#원소를 저장하기 위한 리스트 생성
        

def size( self ):			#집합의 크기
	return len(self.items)		#len() 함수 사용
		
def display(self, msg):			#화면에 출력
	print(msg, self.items)		#메시지 + 집합 내용 출력
    
    
def contains(self, item) :
	return item in self.items
    
def insert(self, elem):
	if elem not in self.items:
    	self.items.append(elem)
        
def delete(self, elem):
	if elem not in self.items:
    	self.items.remove(elem)
        
def union(self, setB):
	setC = set()
    setC.items = list(self.items)
    for elem in setB.items :
    	if elem not in self.items :
        	setC.items.append(elem)
    return setC
    
def interserct(self, setB):
	setC = Set()
    for elem in setB.items :
    	if elem in self.items :
        	setC.items.append(elem)
    return setC

def difference( self, setB)
	setC = set
    for elem in self.items
    	if elem not in setB.items:
        	setC.items.append(elem)
    return setC

 

 

 

4️⃣ Summary of List and SET

• List는 선형 데이터 구조 중 가장 유연한 자료구조이다.
• List는 배열 구조나 링크 구조를 사용하여 구현할 수 있다.
• Set에는 중복 요소가 허용되지 않으며 특정 요소에 대한 정렬이 없다.