리스트, 집합

리스트와 집합은 모든 자료구조와 알고리즘의 기초가 되는 자료구조이다. 따라서 이에 대해 학습해보도록 하겠다

리스트

특징

리스트, 혹은 선형 리스트는 항목들이 차례대로 나열되어 있는 선형 자료구조이다. 리스트들의 항목들은 순서 또는 position을 가진다. 집합과 다른점은, 리스트는 순서가 존재한다는 점이다.

LIST ADT

List()
insert(pos, e)
delete(pos)
isEmpty()
getEntry(pos)
size()
clear()
find(item)
replace(pos, item)
sort()
merge(lst)
display()
append(e)

리스트에서는 위와 같은 기능들을 수행 할 수 있다.
물론 해당 기능들은 파이썬에 이미 내장된 list에 대부분 있거나, 비슷하게 조합해서 쓸 수 있는 기능들이다. 하지만 우리가 평생 파이썬만 쓰고 살 것은 아니기에, 이 기능들에 대한 구현을 알아두는것은 중요하다.

리스트의 구현

리스트는
1. 배열구조
2. 연결된 구조
두 가지 구조로 구현 할 수 있다.

배열구조

Array 구조는 같은 자료형의 데이터를 한번에 만들 떄 사용하는데, 대부분의 프로그래밍 언어에서 사용된다. 접근을 위해 [] 인덱스 연산자를 사용한다. 이는, 자료들이 연속한 주소에 위치하기 때문이다. (컴퓨터 구조 참고)

배열이 아무리 커도 인덱스 번호만 안다면 즉, 주소만 알고 있다면 바로 접급 가능해서 항목접근시간은 O(1)이다. 하지만, 항목에 무언가를 더하거나 빼거나 하는 연산에서는 시간복잡도가 늘어나게 된다.

연결된 구조

linked list라 부르는 물건이다. 추후 구현을 하면서 자세한 설명을 하도록 하겠다.
항목접근의 시간복잡도는 O(k)이다.

파이썬의 리스트

파이썬의 리스트는 C, JAVA의 Array와 다르게 스마트한 동적배열이다. 기존의 배열에서는 미리 배열의 크기를 지정해줘야 했다. 이에 데이터의 양을 가늠할 수 없는 배열이라면, 실제로 사용하게가 어렵다는 단점이 존재했는데, 파이썬 리스트는 이러한 문제점을 신경안쓰고 배열 및 구현 할 수 있다.

파이썬 리스트의 시간복잡도

append()의 시간복잡도 : O(1) * 아주 가끔 모든 용량을 늘려야 추가되는 경우 O(n)

insert() : 모든 항목을 복사하고 중간에 끼워넣어야해서 O(n)이다.
pop() : 위와 동일하다.

구현 코드

class ArrayList:
    def __init__(self):
        self.items = []

    def insert(self, pos, elem):
        self.items.insert(pos, elem)

    def delete(self, pos):
        return self.items.pop(pos)

    def isEmpty(self):
        return self.size() == 0

    def getEntry(self, pos):
        return self.items[pos]

    def size(self):
        return len(self.items)

    def clear(self):
        self.items = []

    def find(self, item):
        return self.items.index(item)

    def replace(self, pos, elem):
        self.items[pos] = elem

    def sort(self):
        self.items.sort()

    def merge(self, lst):
        self.items.extend(lst)

    def display(self, msg='ArrayList'):  # default argument
        print(msg, self.size(), self.items)

특별히 어려운 기능은 없기에 설명은 생략하도록 하겠다.

집합

특징

리스트와 유사한 개념이나, 집합은 원소의 중복을 허용하지 않으며, 원소사이의 순서가 없다.

Sets ADT

set()
size()
contains(e)
insert(e)
delete(e)
equals(setB)
union(setB) - 합집합 연산
intersect(setB) - 교집합 연산
difference(setB) - 차집합 연산
display()

구현 코드

class Set:
    def __init__(self):
        self.items = []

    def size(self):
        return len(self.items)

    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 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 intersect (self, setB):
        setC = Set()
        for elem in setB.items:
            if elem in self.items:
                setC.items.append(elem)
        return setC

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

집합만의 독특한 연산인 합집합, 교집합, 차집합 함수에 대한 설명을 하겠다

합집합

    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

합집합을 저장할 새로운 집합 C를 선언한다. C에 자신의 원소들을 전부 저장한 후 집합 B에 있는 원소들을 전부 확인하며 현재 자신의 집합에 없는 원소들이라면, 전부 c에 저장한다.

교집합

    def intersect (self, setB):
        setC = Set()
        for elem in setB.items:
            if elem in self.items:
                setC.items.append(elem)
        return setC

교집합을 저장할 새로운 집합 C를 선언한다. 집합 B의 원소를 모두 확인하면서, 해당 원소가 A 자신의 원소에도 있는 원소라면 C에 넣는다.

차집합

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

차집합을 저장할 새로운 집합 C를 선언한다. 그리고 교집합과 반대로 B의 원소들을 모두 확인하면서, 자기 자신의 원소와 중복되는원소가 없다면, C에 저장한다.

연결리스트

특징

맨 위에서 리스트 부분의 설명을 보면 리스트는 연결된 구조, 즉 연결리스트로 구현할 수 있다고 설명한 부분이 있다. 연결리스트는 말 그대로 연결된 리스트이다.

• 파이썬의 리스트만 쓰다보면 연결리스트가 그다지 필요없다고 생각할지도 모르지만, 기본 원리는 알아두는것이 많이 도움된다.
• 약간의 리서치 결과, 파이썬의 리스트도 일단은 연결리스트라고 한다. 이는 추후 검증이 필요한 정보이다.

장점과 단점

1. 용량이 제한적이지 않다는점이다.
   배열구조는 순서대로 자료가 담겨있기에 정해진 용량이 벗어난다면 전체를 복사하고 새 배열을 만드는 복잡한 과정이 필요하지만, 연결리스트는 주소만 서로 link해주면 되기에 별 문제가 생기지 않는다.

2. 삽입 삭제가 자유롭다.
   배열구조에서는 삭제나 삽입을 수행하면 전체의 위치를 한번씩 밀거나 당기거나 하는 연산이 필요했다. 하지만 연결리스트는 삽입한다면 둘의 연결 주소만 바꿔주고, 삭제한다면 둘의 연결 주소만 삭제해주면 된다. 따라서 시간복잡도는 O(1)이 된다.

3. 항목접근 시간이 길다 (단점)
   배열에서는 인덱스를 통해 항목에 바로 접근이 가능했지만, 연결리스트에서는 헤드포인터에서 하나씩 접근해 들어가야하는 단점이 있다.

연결리스트의 구조

Node

연결된 구조에서 하나의 상자를 Node라 한다. Node에는 값을 가지는 Data Field와 주소를 가지는 Link Field가 존재한다. 이는 앞으로 연결리스트, 스택, 큐, 디큐를 넘어 그래프에서도 주로 사용되는개념이다.

Head Pointer

연결리스트는 첫번째 노드만 알면 링크로 다른 모든 연결된 노드들에 접근할 수 있다. 따라서 이 첫번째 node의 주소를 반드시 저장해야한다. 이를 저장하는 것을 바로 Head Pointer라고 한다. 그리고 마지막 node의 link는 None으로 지정, 연결이 더 없고 여기가 끝임을 표기한다.

연결리스트에는

• 단순연결리스트
• 이중연결리스트
• 원형연결리스트

총 3종류가 있다. 이는 추후 자료구조를 다루면서 설명하도록 하겠다.

연결리스트의 구현

class Node:
    def __init__(self, elem, link):
        self.data = elem
        self.link = link


class LinkedList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head is None

    def size(self):
        node = self.head
        count = 0
        while node is not None:
            node = node.link
            count += 1
        return count

    def getNode(self, pos):
        if pos < 0:
            return None
        node = self.head
        while pos > 0 and node is not None:
            node = node.link
            pos -= 1
        return node

    def getEntry(self, pos):
        node = self.getNode(pos)
        if node is None:
            return None
        else:
            return node.data

    def replace(self, pos, elem):
        node = self.getNode(pos)
        if node is not None:
            node.data = elem

    def find(self, data):
        node = self.head
        while node is not None:
            if node.data == data:
                return node
            node = node.link
        return node

    def insert(self, pos, elem):
        before = self.getNode(pos - 1)
        if before is None:
            self.head = Node(elem, self.head)
        else:
            node = Node(elem, before.link)
            before.link = node

    def delete(self, pos):
        before = self.getNode(pos - 1)
        if before is None:
            if self.head is not None:
                self.head = self.head.link
        elif before.link is not None:
            before.link = before.link.link


    def object__repr__(self):
        pass

Class Node

노드 클라스에서는 노드를 생성하게 된다. self.data에는 원소값 elem, self.link에는 link값을 넣는다. link값은 Default Argument를 사용하여 아무것도 없다면 None, 무언가를 넣는다면 그 값이 들어가도록 한다.

getNode

    def getNode(self, pos):
        if pos < 0:
            return None

        node = self.head
        while pos > 0 and node is not None:
            node = node.link
            pos -= 1
        return node

노드를 구하는 연산이고, 삽입 삭제에 주로 사용된다.

node를 self.head와 연결된 것, 즉 시작노드로 설정한다. 그 후 pos값을 하나씩 줄이면서 노드를 다음노드로 이동한다. pos가 0일때 그 결과물을 반환한다.

삽입, 삭제 연산

우선 삽입연산 insert 이다.

    def insert(self, pos, elem):
        before = self.getNode(pos -1)  # the one before the place
        if before == None:
            self.head = Node(elem, self.head)
        else:
            node = Node(elem, before.link)
            before.link = node

before라는 값을 설정하여 삽입하고자 하는 위치 바로 직전의 노드를 찾는다. 그 후 다음과 같은 과정을 통해 수행한다.
1. 이전노드가 없는경우
이전노드가 None인 경우는 단 하나, 현재 삽입 위치가 리스트의 맨 앞인 경우이다. 따라서 이런 경우네는 self.head에는 첫번째 원소이자 새로 삽입할 node를 넣어준다. 이떄 node의 링크필드에는 self.head의 값, 즉 자기 자신의 주소를 넣어야한다.

2. 이전노드가 있는 경우
   before 값이 있는 경우 node 변수에 새로 만든 node를 추가한다. 이 떄 node는 before.link가 가르키고 있던 값을 추가한다.
   그 후, before.link는 현재 node로 변경한다.

1, 2, 3, 4 의 리스트가 있고 우리가 2와 3 사이에 값을 끼워넣고자 한다. 이럴떄 우리는 새로운 값 노드를 생성하고 그 노드의 주소에는 2가 가지고 있던 주소 3을 넣어서 새로운 노드가 3과 연결되도록 하는것이다.

삭제연산 delete이다.

    def delete(self, pos, elem):
        before = self.getNode(pos - 1)  # the one before the place
        if before == None:
            if self.head is not None:
                self.head = self.head.link
        elif before.link is not None:
            before.link = before.link.link

insert와 마찬가지로 before에 이전값을 찾는다.
1. 이전값이 없는경우
1-1 self.head가 None은 아닌경우
이 경우, 리스트가 아예 비어있는 리스트는 아니므로, self.head 의 값을 self.head가 가지고 있는 link 값으로 변경한다.

2. 이전값이 있는 경우
   before.link의 값을 before.link가 가지고 있던 link의 값으로 변경한다

1 2 3 이 있을떄 2를 지운다고 하면 우리는 2가 가지고 있던 3에 대한 링크정보를 1에 링크에 준다는 의미이다.

그렇다면 한가지 의문이 생길 수 있다. 지운 값은 어디가는걸까? 파이썬 에서는 이를 걱정할 필요가 없다. 자동적으로 메모리 정리를 해주기 때문이다. (Garbage Collection)

시간복잡도

코드를 보면 알겠지만, 삭제 혹은 삽입 자체는 시간복잡도가 O(1)이다. 하지만 실제로는 그렇지 않다. before의 값을 찾아햐하기 때문이다. 우리는 이 before값을 getNode를 통해 찾는데, getNode의 코드는 하나씩 탐색하는 코드이다. 따라서 getNode는 O(n)만큼의 시간이 걸린다. 결국, 삽입 삭제연산은 O(n)만큼 걸린다고 할 수 있다.

마치며

이번시간에는 리스트와 집합, 그리고 연결리스트에 대해 알아보았다. 연결리스트는 추후에도 자주 사용되는 개념이기에 잘 알아두면 좋을것이다.