자료구조 및 실습 - [5] 집합 Set (1)

집합 ADT

집합 ADT는 유일한 개체들을 담는 용기를 모델링한다. 우리가 중고등학교 시절에 배운 집합과 같다. 중복된 개체는 존재할 수 없고 오직 유일한 개체만 포함될 수 있다.

 

---

집합 ADT 메서드

합집합 union(B) : 집합 B와의 합집합을 반환

교집합 intersect(B) :집합 B와의 교집합을 반환

차집합 subtract(B) : 집합 B를 차감한 차집합을 반환

 

집합 A와 B에 관한 주요 작업의 실행시간은 최대 O(|A| + |B|)이 되어야 한다!!

- 일반 메서드

  integer size()

  boolean isEmpty()

  iterator elements()

 

- 질의 메서드

  boolean member(e) : 개체 e가 집합의 원소인지 여부를 반환

  boolean subset(B) : 집합이 집합 B의 부분집합인지 여부를 반환

  

- 갱신 메서드

  addElem(e) : 집합에 원소 e를 추가

  removeElem(e) : 집합으로부터 원소 e를 삭제

 

- 예외

  emptySetExeption() : 비어 있는 집합에 대해 삭제 혹은 첫 원소를 접근 시도할 경우 발령

 

---

집합 ADT 구현

집합을 연결리스트로 구현할 수 있다. 연결리스트의 노드 하나는 집합원소를 표현하며, 효율을 위해 헤더 및 트레일러 이중연결리스트를 사용하는 것을 추천한다!

 

또한 원소들은 일정한 순서에 의해 정렬 (오름차순, 내림차순 등)되어 저장된다.

 

성능

모두 O(|A| + |B|) 시간에 수행되며, 이는 addLast 작업을 O(1) 시간에 수행한다는 전제 하에 보장된다. 

집합을 이중연결리스트로 구현, 혹은 단일연결리스트로 구현할 경우 C의 마지막 노드 위치를 관리한다.

 

합집합, 교집합, 차집합, 소속과 부분집합의 의사코드를 확인하자.

합집합의 의사코드

합집합의 의사코드

 

교집합의 의사코드

교집합의 의사코드

차집합의 의사코드

차집합의 의사코드

소속과 부분집합의 의사코드

소속과 부분집합의 의사코드

class Node:
  def __init__(self,data,prev=None,next = None):
    self.data = data
    self.prev = prev
    self.next = next

#이중연결리스트로 구성된 집합
class DLset:
  def __init__(self):
    self.header = Node("Header")
    self.trailer = Node("Trailer",self.header)
    self.header.next = self.trailer
    self.setsize = 0

  def isEmpty(self):
    if self.setsize ==0:
      return True
    else:
      return False

  def printset(self):
    if self.setsize == 0:
      print("공집합")
    else:
      target = self.header
      for i in range(self.setsize):
        target = target.next
        print(target.data,end=" <=> ")

  # def member(self,e):
  #   if self.setsize == 0:
  #     return False

  #   else:
  #     target = self.header
  #     for i in range(self.setsize):
  #       target = target.next
  #       if target.data == e:
  #         return True
  #   return False
  def member(self,e):
    if self.setsize ==0:
      return False
    target = self.header.next
    while True:
      a = target.data
      if a<e:
        if target.next == None:
          return False
        else:
          target = target.next
      elif a>e:
        return False
      else:
        return True
  
  def addelem(self,e):
    # if self.setsize==0:
    #   newnode = Node(e,self.header,self.trailer)
    #   self.header.next= newnode
    #   self.trailer.prev = newnode

    
    # else:
    #   target = self.header
    #   newnode = Node(e) #삽입할거 생성
    #   for i in range(self.setsize):
    #     target = target.next
    #   target.next.prev
    #   target.next = newnode #연결1
    #   newnode.prev = target #연결2

    # print(f"before : {self.trailer.prev.prev.data}")#" <=> {self.trailer.prev.data}")" <=> {self.trailer.data}")
    newnode = Node(e,None,self.trailer)#Newnode_prev : None / Newnode_next = trailer
    prev_trailer = self.trailer.prev
    newnode.prev = prev_trailer#Newnode_prev : 전에 trailer에 연결됐었던 노드  / Newnode_next = trailer
    prev_trailer.next = newnode
    self.trailer.prev = newnode #trailer설정완료
    #print(f"After : {self.trailer.prev.prev.data} <=> {self.trailer.prev.data} <=> {self.trailer.data}")

    
    self.setsize +=1
    

  def removeElem(self, e):
    if self.setsize==0:
      print("Invalid position")
    
    else:
      target = self.header
      for i in range(self.setsize):
        target = target.next
        if target.data == e:
          break
      prevnode = target.prev
      nextnode = target.next
      d = target.data
      prevnode.next = nextnode
      nextnode.prev = prevnode
      del(target)
      self.setsize -=1

  def union(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        c.append(a)
        self.removeElem(a)
      elif a>b:
        c.append(b)
        B.removeElem(b)
      else:
        c.append(a)
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      c.append(a)
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      c.append(b)
      B.removeElem(b)
    return c
  
  def intersect(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        self.removeElem(a)
      elif a>b:
        B.removeElem(b)
      else:
        c.append(a)
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      B.removeElem(b)
    return c

  def subtract(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        c.append(a)
        self.removeElem(a)
      elif a>b:
        B.removeElem(b)
      else:
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      c.append(a)
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      B.removeElem(b)
    return c
  
  def subset(self,B):
    if self.setsize ==0:
      return True
    target = self.header.next
    while True:
      if B.member(target.data):
        if target.next == None:
          return True
        else:
          target = target.next
      else:
        return False

>>> A = DLset()
>>> B = DLset()
>>> A.addelem(1)
>>> A.addelem(2)
>>> A.addelem(3)
>>> B.addelem(2)
>>> B.addelem(3)
>>> B.addelem(4)
>>> A.union(B)

[1, 2, 3, 4]