240105 동계 모각코 3차

모각코는 블로그에 배운 개념을 정리하고, 문제를 풀며 틀린 부분이나 새롭게 알게 된 부분이 있는 문제만 기록하기로 하였다. 

 

앞에서 배웠던 배열은 크기가 정해져 있고, 따라서 데이터의 개수가 바뀔 경우 여러가지 배열을 그 때마다 만들어줘야 한다. 

크기가 정해져 있지 않은 배열이 바로 동적 배열이다. 파이썬의 list가 그 예시이다. 

 

 

 

 

코드 설명은 다음과 같다.

동적 배열을 구현하기 위한 클래스를 정의 한후, 초기화 메서드에서 빈 배열 ( 파이썬의 배열은 동적 배열이다. ) 을 만든다. 그리고 

각 매서드를 구현하는데 각 매서드의 구현방법은 크게 어렵지 않았다. 

 

 

 

단일 연결 리스트 .

1학기 자료구조와 2학기 알고리즘, 그리고 과목을 가리지 않고 기본적으로 등장하는 자료구조다. 

단일 연결 리스트와 뒤에 배울 동적배열들을 학습하기 위해 Node의 정의부터 알아보자. 많이 들어본 말이긴 하지만 정확한 개념을 공부해 보는것은 처음이다. 노드는 간단하게 정보를 담는 공간이라고 생각하면 된다. 그리고 단일 연결 리스트는 이러한 노드가 연결되어 만들어지는 구조이다.

 

단일 연결 리스트의 삽입. tail 뒤쪽에 값을 삽입한다고 가정하면 새로운 노드는 그냥 들어오면 된다. 그러나 새로운 노드가 중간에 들어오게 된다면 일단 삽입되는 노드를 맨 끝 노드에 연결해놓고, tail 노드를 변경해주면 된다. 

 

 

비슷한 방법으로 head 앞에 값을 추가하는 것도 구현할 수 있다.

 

하지만 head 뒤에 노드를 추가하는 것은 조금 복잡할 수 있다.

1. 새로운 노드를 만든다.

2. 새로운 노드의 next 값을 head의 next에 있던 값으로 설정한다. 

3. head의 next 값을 새로운 노드로 변경한다. 

 

function SLL.insert_after_head(num)
  set new_node = node(num)            # Step 1. 노드 만들기
  new_node.next = SLL.head.next       # Step 2. 새로운 노드의 next 값 변경
  SLL.head.next = new_node            # Step 3. Head의 next 값 변경

 

어려운 듯 하지만 , 알고리즘 시간에 배운 기억을 토대로 이해할 수 있었다. 

삭제도 똑같은 메커니즘으로 진행하면 된다. 

하지만 탐색은 조금 다르다. linkedlist 에서 탐색 연산은 head에서 시작하여 쭉 따라가야 한다. index 가 없기 때문이다.

 

직접 코드를 구현하는 문제와 동작을 예상하는 문제들이 있었다. 2학기 때 모두 과제로 또는 시험으로 풀어봤던 문제들이기에 큰 어려움은 없었다.

 

이중 연결 리스트. 

단일 연결 리스트의 단점으로, 앞으로의 이동만 가능하다는 점이 있었다. 이 점을 보완하여, next를 확장하여 특정 노드의 뒷 노드만을 이어주는 것이 아니라 앞 노드도 연결하는 prev 를 추가해 이어줄 수 있게 하자. 

 

 

보통의 list는 모두 이중 연결 리스트이다. 하지만 파이썬에는 이중 연결 리스트 구현체에 해당하는 list 라는 내장 클래스가 없으므로, 이 자료구조를 사용하기 위해서는 직접 다음과 같이 class를 만들어 줘야 한다. 

 

# Node 클래스를 만들어줍니다.
class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None 
        self.prev = None


# 이중 연결 리스트 클래스를 만들어줍니다.
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.node_num = 0
  
    def push_front(self, new_data):   # 원소를 첫 번째 위치에 넣어줍니다.
        new_node = Node(new_data)     # 새로운 노드를 만들어줍니다.
        new_node.next = self.head     # 새로운 노드의 next 값을 head로 바꿔줍니다.

        if self.head != None:         # 기존 리스트가 비어있지 않았다면
            self.head.prev = new_node # 이전 head의 prev값을 바꾼 뒤
            self.head = new_node      # head값을 변경해줍니다.
            new_node.prev = None
    
        else:                         # 기존 리스트가 비어있었다면
            self.head = new_node      # head, tail을 새로 설정해줍니다.
            self.tail = new_node
            new_node.prev = None
        
        self.node_num += 1

    def push_back(self, new_data):    # 원소를 맨 끝 위치에 넣어줍니다.
        new_node = Node(new_data)     # 새로운 노드를 만들어줍니다.
        new_node.prev = self.tail     # 새로운 노드의 prev 값을 tail로 바꿔줍니다.

        if self.tail != None:         # 기존 리스트가 비어있지 않았다면
            self.tail.next = new_node # 이전 tail의 next값을 바꾼 뒤
            self.tail = new_node      # tail 값을 변경해줍니다.
            new_node.next = None

        else:                         # 기존 리스트가 비어있었다면
            self.head = new_node      # head, tail을 새로 설정해줍니다.
            self.tail = new_node
            new_node.next = None

        self.node_num += 1

    def pop_front(self):              # 첫 번째 수를 빼면서 동시에 그 수를 반환합니다.
        if self.head == None:
            print("List is empty")
    
        elif self.head.next == None:  # 노드가 하나 남았다면
            temp = self.head

            self.head = None          # head값을 None으로 바꿔주고
            self.tail = None          # tail값도 None으로 바꿔주고
            self.node_num = 0         # 원소의 수도 0개로 변경해줍니다.
            return temp.data

        else:
            temp = self.head
            temp.next.prev = None     # 새로 head가 될 노드의 prev값을 지워줍니다.
            self.head = temp.next     # head값을 새로 갱신해주고
            temp.next = None          # 이전 head의 next 값을 지워줍니다.

            self.node_num -= 1
            return temp.data
  
    def pop_back(self):               # 맨 끝에 있는 수를 빼면서 동시에 그 수를 반환합니다.
        if self.tail == None:
            print("List is empty")

        elif self.tail.prev == None:  # 노드가 하나 남았다면
            temp = self.tail

            self.head = None          # head값을 None으로 바꿔주고
            self.tail = None          # tail값도 None으로 바꿔주고
            self.node_num = 0         # 원소의 수도 0개로 변경해줍니다.
            return temp.data

        else:
            temp = self.tail
            temp.prev.next = None     # 새로 tail이 될 노드의 next값을 지워줍니다.
            self.tail = temp.prev     # tail값을 새로 갱신해주고
            temp.prev = None          # 이전 tail의 prev 값을 지워줍니다.

            self.node_num -= 1
            return temp.data

    def size(self):
        return self.node_num

    def empty(self):
        return self.node_num == 0

    def front(self):                  # 첫 번째 수를 반환합니다.
        if self.head == None:
            print("List is empty")
        else:
            return self.head.data
  
    def back(self):                   # 맨 끝에 있는 수를 반환합니다.
        if self.tail == None:
            print("List is empty")
        else:
            return self.tail.data

 

 

코드가 꽤 길지만, 각 메서드들은 어렵지 않게 구현할 수 있다. 

push, pop, size, empty, front, back

각각은 삽입, 삭제, 크기 반환, 비었다면 True 반환, 맨 앞 데이터 반환, 맨 뒤의 데이터 반환.

이런 역할을 하고 있다. 

 

 

iterator ( 반복자 ) 

간단하게 말해 연결 리스트와 별도로 자유 자재로 값을 순해할 수 있는 자료구조이다. 배열의 index와 유사하게, linkedlist 에서는 iterator를 사용한다. 연결 리스트를 돌아다니는 하나의 포인터라고 이해하면 될 것 같다. 

 

# Node 클래스를 만들어줍니다.
class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None 
        self.prev = None


# 이중 연결 리스트 클래스를 만들어줍니다.
class DoublyLinkedList:
    def __init__(self):
        self.END = Node(-1)                # 구현의 편의를 위해 dummy 값을 넣어놓고 시작합니다.
        self.head = self.END
        self.tail = self.END
  
    def push_front(self, new_data):        # 원소를 첫 번째 위치에 넣어줍니다.
        new_node = Node(new_data)          # 새로운 노드를 만들어줍니다.
        new_node.next = self.head          # 새로운 노드의 next 값을 head로 바꿔줍니다.

        self.head.prev = new_node          # 이전 head의 prev값을 바꾼 뒤
        self.head = new_node               # head값을 변경해줍니다.
        new_node.prev = None

    def push_back(self, new_data):         # 원소를 맨 끝 위치에 넣어줍니다.
        if self.begin() == self.end():     # 만약 리스트가 비어있다면
            self.push_front(new_data)      # 맨 앞에 원소를 넣어주는 것과 로직이 같습니다. 
            
        else:
            new_node = Node(new_data)      # 새로운 노드를 만들어줍니다.
            new_node.prev = self.tail.prev # 새로운 노드의 prev 값을 맨 끝 dummy의 prev로 변경해준 뒤
            self.tail.prev.next = new_node # 맨 끝 dummy의 next로 새로운 노드를 연결해주고
            new_node.next = self.tail      # 새로운 노드의 next값을 맨 끝 dummy 값으로 바꿔주고
            self.tail.prev = new_node      # 맨 끝 dummy의 prev값을 새로운 노드로 변경합니다.

    def erase(self, node):
        next_node = node.next

        if node == self.begin():           # 만약 head가 삭제되어야 한다면
            temp = self.head          
            temp.next.prev = None          # 새로 head가 될 노드의 prev값을 지워줍니다.
            self.head = temp.next          # head값을 새로 갱신해주고
            temp.next = None               # 이전 head의 next 값을 지워줍니다.

        else:                              # head가 삭제되는 것이 아니라면
            node.prev.next = node.next     # 바로 전 노드의 next값을 바꿔주고
            node.next.prev = node.prev     # 바로 다음 노드의 prev값을 바꿔주고
            node.prev = None               # 해당 노드의 prev 와 
            node.next = None               # 해당 노드의 next 값을 모두 지워줍니다.

        return next_node
    
    def insert(self, node, new_data):
        if node == self.end():             # node가 맨 끝 위치에 있다면
            self.push_back(new_data)       # 맨 뒤에 원소를 추가합니다.   

        elif node == self.begin():         # node가 맨 앞 위치에 있다면
            self.push_front(new_data)      # 맨 앞에 원소를 추가합니다.

        else:                              # 그렇지 않다면
            new_node = Node(new_data)      # 새로운 노드를 만들어줍니다.
            new_node.prev = node.prev      # 새로운 노드의 prev값을 node의 prev값으로 하고
            new_node.next = node           # 새로운 노드의 next값을 node로 하고
            node.prev.next = new_node      # node의 prev의 next값을 새로운 노드로 변경하고
            node.prev = new_node           # node의 prev 값을 새로운 노드로 변경합니다.

    def begin(self):
        return self.head
    
    def end(self):
        return self.tail


l = DoublyLinkedList()            # 문자를 관리할 list를 선언하고 => 빈 list
# 이중 연결 리스트에 'a', 'b', 'c'를 순서대로 추가합니다.
l.push_back('a')
l.push_back('b')
l.push_back('c')

# iterator를 list의 맨 앞에 위치시킵니다.
it = l.begin()

print(it.data)    # 원소 값을 출력합니다. ('a')
it = it.next      # 한 칸 뒤로 이동합니다.
print(it.data)    # 원소 값을 출력합니다. ('b')
it = it.prev      # 한 칸 앞으로 이동합니다.
print(it.data)    # 원소 값을 출력합니다. ('a')

it = l.erase(it)  # 원소 'a'를 제거합니다.
print(it.data)    # 원소 값을 출력합니다. ('b')

l.insert(it, 'd') # 원소 'd'를 추가합니다.

# list에 들어있는 원소 값을 순서대로 출력합니다.
it = l.begin()
while it != l.end(): # 'd' 'b' 'c'
    print(it.data, end="")   # it가 가리키는 주소에 담긴 데이터 출력
    it = it.next     # 다음 위치로 이동

 

위와 같이, 코드를 작성해 볼 수 있을것 같다 .