[자료 및 알고리즘] 3. 리스트와 집합 (파이썬)

리스트란?

 

순서를 가진 항목들의 모임 (선형 자료구조)

항목들은 "위치를" 가진다.

 

Stack, Queue, Deque와의 차이점

요소들을 삽입할 때 전단과 후단에서만 넣을 수 있으나, 리스트는 어디서든 항목의 삽입과 삭제가 가능하다.

 

리스트의 추상 자료형

 

데이터

같은 유형의 순서 있는 모임이면 다 넣을 수 있음

 

연산

- insert (pos,e) : pos 위치에 새로운 요소 e를 삽입한다.

- delete(pos) : pos 위치에 있는 요소를 꺼내고 (삭제) 반환한다.

- isEmpty() : 리스트가 비어 잇는지를 검사한다.

- isFull() : 리스트가 가득 차 있는지를 검사한다.

-getEntry(pos) : pos 위치에 있는 요소를 반환한다.

 

리스트 구현 방법

 

배열 구조

- 구현이 간단

- 항목 접근이 O(1)

- 삽입, 삭제시 오버헤드

- 항목의 개수 제한

 

연결된 구조(포인터나 링크)

-구현이 복잡

-항목 접근이 O(n)

- 삽입, 삭제가 효율적

- 크기가 제한되지 않음

 

파이썬 리스트

 

파이썬 리스트 선언 

A = [1,2,3,4,5]
B = [0] * 5

 

리스트 크기 구하기

len(A)

 

리스트 크기 늘리기

A.append(6)		#뒤에다가 6을 넣는다.
A.insert(0,0)	#(0(앞쪽)번째 인덱스에 0{뒷쪽)을 넣는다. 나머지는 밀려나감
A.insert(9)		#9를 맨 뒷쪽에 넣는다.

 

파이썬 리스트에서 크기가 꽉찼을 경우

 

1. 필용한 양보다 넉넉한 크기의 메모리를 사용

용량을 원래 잡는데 부족하면 기존 배열보다 큰 배열을 할당한다.

 

2.기존의 배열을 새로운 배열에 복사한 뒤, 항목을 삽입

 

3. 기존 배열 해제, 리스트로 새 배열을 사용한다.

 

 

연산들의 시간 복잡도

- append(e) => O(1) , 가끔 꽉차서 복사할 경우 => O(n)

- insert(pos, e) => O(n)

- pop(pos) => O(n)

 

배열로 구현한 리스트

용량이 구조한 리스트의 구조

=> array[capacity]와 size가 필요함

 

배열로 구현된 리스트

 

- 함수 버전

capacity = 100;
array = [None]*capacity
size = 0;

def isEmpty():
    if size == 0 : return True
    else : return False

def isFull():
    return array[pos]

def getEntry(pos):
    if 0 <= pos <size :
        return array[pos]
    else : return None
    
def insert(pos,e):
    global size
    if not isFull() and 0 <= pos <= size :
        for i in range(size, pos-1) :
            array[i] = array[i-1]
        array[pos] = e
        size += 1
    else :
        print("리스트 overflow 또는 유효하지 않은 삽입 위치")
        exit()

def delete(pos) :
    global size
    if not isEmpty() and 0 <= pos < size :
        e = array[pos]
        for i in range(pos, size-1) :
            array[i]=array[i+1]
        size -= 1
        return e
    else :
        print("리스트 underflow 또는 유효하지 않은 삭제 위치")
        exit()

 

-클래스 구현 방법

class ArrayList:

   def __init__(self, capacity=100):
       self.capacity = capacity
       self.array = [None]*capacity
       self.size = 0
       
   def isEmpty(self):
       return self.size==0
       
   def isFull(self):
       return self.size==self.capacity
       
   def getEnty(self, pos):
       if 0 <= ps < self.size :
           return self.array[pos]
       else : return None
   
   def insert(self,pos,e):
       if not self,isFull() and 0 <= pos <= self.size :
           for i in range(self.size, pos, -1):
               self.array[i] = self.array[i-1]
           self.array[pos]=e
           self.size += 1
       else : pass
       
   def delete(self, pos):
       if not self.isEmpty() and 0 <= pos < self.size :
           e=self.array[pos]
           for i in range(pos, self.size-1) :
               self.array[i] = self.array[i]
           self.size -= 1
           return e
       else : pass
   
   def __str__(self) :
       return str(self.array[0:self.size])

 

집합이란?

 

원소들의 중복을 허용하지 않음

원소들 사이에 순서가 없다 (선형 자료구조가 아님)

 

집합의 추상 자료형

데이터

같은 유형의 유일한 요소들의 모임. 원소들은 순서가 없으나 서로 비교할 수 는 있어야 한다.

 

연산

- insert (e) : 새로운 원소 e를 삽입한다. 중복하면 실행 x        =>중복 검사, O(n)

- delete(e) : 원소 e를 집합에서 삭제하고 반환한다.               => 삭제할 원소를 찾기 O(n)

- contains(e) : 집합이 원소 e를 포함하는지를 검사한다.        => 순차탐색, O(n)

- isEmpty() : 공집합인지 확인한다.

- isFull() : 집합이 준 크기만큼 가득 차 있는지를 검사한다.

- union(setB) setB와의 합집합을 만들어 반환한다.                => O(n^2)

- intersect(setB) setB와의 교집합을 만들어 반환한다.           => O(n^2)

- difference(setB) setB와의 차집합을 만들어 반환한다.         => O(n^2)

 

집합 구현하기

class ArraySet :
    
    #생성자, isEmpty(), isFull(), __str__()은 ArrayList 클래스와 동일
    
    def contains(self,e) :
        for i in range(self.size):
            if self.array[i]==e :
                return True
            return False
    
    def insert(self,e) :
        if not self.contains(e) and not self.isFull() :
            self.array[self.size] = e
            self.size+=1
    
    def delete(self,e) :
        for i in range(self.size) :
            if self.array[i]==e :
                self.array[i]==e :
                self.array[i] = self.array[self.size-1]
                self.size -= 1
                return
    
    def union(self, setB) :
        setC=ArraySet()
        for i in range(self.size) :
            setC.insert(self.array[i])
        for i in range(setB.size) :
            if not SetC.contains(setB.array[i]) :
                setC.insert(setB.array[i]
        return setC
    
    def intersect(self, setB) :
        setC=ArraySet()
        for i in range(self.size) :
            if setB.contains(self.array[i]) :
                setC.insert(self.array[i])
        return setC
    
    def difference(self, setB);
        setC=ArraySet()
        for i in range(self.size):
            if not setB.contains(self.array[i]) :
                setC.insert(self.array[i])
        retrun setC