📖 학습주제

자료구조/알고리즘 풀기(2)

---

추상적 자료구조(Abstact Data Structure)

자료구조의 내부구현은 숨겨두고 밖에서 보이는 데이터(정수, 문자열, 레코드 등)와 연산(삽입, 삭제, 순회, 정렬, 탐색 등)만을 제공하는 것

연결 리스트

연결 리스트(Linked List)

앞에 있는 것이 뒤에 있는 것을 가리키도록 되어있는 배열

연결 리스트는 보는 것과 같은 노드(Node)로 이루어져 있다.

• 데이터(Data) : 노드가 가지고 있는 데이터, 여러가지 구조들(문자열, 레코드, 연결 리스트 등)로 표현이 가능하다.
• 링크(Link) : 다음 노드를 가리킨다.(다음 노드로 연결됨)

연결 리스트는 다음과 같이 여러 노드로 이루어져 있으며 가장 앞에 있는 노드를 Head, 가장 뒤에 있는 노드를 Tail이라 칭한다.

• 노드 & 연결 리스트

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

연결리스트의 연산 정의

특정 원소 참조

def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr

리스트 순회

def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

길이 얻어내기

 def getLength(self):
        return self.nodeCount

원소 삽입

def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True

원소 삭제

def popAt(self, pos):
    data = 0
    if pos < 1 or pos > self.nodeCount:
        return False
            
    if self.nodeCount == 1:
        data = self.head.data
        self.head = None
        self.tail = None
                
    else:     
        if pos == 1:
            data = self.head.data
            self.head = self.head.next
                
        elif pos == self.nodeCount:
            prev = self.getAt(pos-1)
            data = prev.next.data
            prev.next = None
            self.tail = prev
        else:
            prev = self.getAt(pos-1)
            data = prev.next.data
            prev.next = prev.next.next
                
    self.nodeCount -= 1
    return data

두 리스트 합치기

def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

배열과 연결 리스트 비교

	배열	연결리스트
저장공간	연속한 위치	임의의 위치
특정 원소 참조	매우 간편(O(1))	선형탐색과 유사(O(n))

Dummy Node 이용

삽입과 삭제가 유연한 연결 리스트의 장점을 살릴 수 있다.

Dummy Node를 가지는 연결 리스트의 구현

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        data = 0
        curr = prev.next
        
        if prev.next == None:
            return None
        
        elif curr.next == None:
            data = curr.data
            prev.next = None
            self.tail = prev
            
        else:
            data = curr.data
            prev.next = curr.next
            
        self.nodeCount -= 1
        return data
        


    def popAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return False
        return self.popAfter(self.getAt(pos-1))

양방향 연결 리스트(DLoubly Linked List)

한 방향으로만 갈 수 있었던 연결 리스트의 단점을 보완하고자 양방향으로 링크가 있는 연결 리스트를 사용함
역방향 순회가 가능하고 양 끝에 더미를 둠

양방향 연결 리스트의 구현

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None
        
    
    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr
        
        
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
        
        
    def popAfter(self, prev):
        curr = prev.next
        data = curr.data
        prev.next = curr.next
        curr.next.prev = curr.prev
        self.nodeCount -= 1
        return data


    def popBefore(self, next):
        curr = next.prev
        data = curr.data
        next.prev = curr.prev
        curr.prev.next = curr.next
        self.nodeCount -= 1
        return data


    def popAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            raise IndexError
        return self.popAfter(self.getAt(pos-1))

---

스택(Stack)

자료를 보관할 수 있는 선형 구조
데이터를 넣을 때 한 쪽 끝에서 밀어넣고(push)
꺼낼 때는 같은 쪽에서 깨낸다.(pop)
-> 나중에 들어 온 것이 먼저 나온다.(Las In First Out)

자주 발생하는 스택 오류

• 스택 언더플로(Stack Underflow) : 비어있는 스택에서 원소를 꺼내려고 함
• 스택 오버플로(Stack Overflow) : 가득 차있는 스택에서 원소를 넣으려고 함

스택의 연산정의

size() : 스택에 들어있는 원소의 수
isEmpty() : 스택이 비어있는지 확인
push(x) : x를 스택에 추가
pop() : 스택 가장 위에 저장된 원소를 제거 및 반환
peek() : 스택 가장 위에 저장된 원소를 반환(제거 x)

스택 구현 방법

배열 이용

class ArrayStack:

	def __init__(self):
		self.data = []

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

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

	def push(self, item):
		self.data.append(item)

	def pop(self):
		return self.data.pop()

	def peek(self):
		return self.data[-1]

연결 리스트 이용

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()

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

	def push(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

---

어제보다 확 어려워진거같은데 기분 탓인가. 어쩌겠어 해내야지