[DEV] 2주차. 자료구조/알고리즘(2)

1. 연결 리스트 Linked Lists

추상적 자료구조

• 자료구조의 내부 구현은 숨겨두고, data와 연산의 집합만 보여주는 자료구조

• data
  • ex) 정수, 문자열, 레코드, …
• A set of operations
  • 삽입, 삭제, 순회, …
  • 정렬, 탐색, …

기본적 연결 리스트

• Node
  • data
    • 문자열, 레코드, 다른 연결 리스트 등이 올 수 있음
  • link (next)
• 추상적 자료구조를 만들기 위해 2개의 클래스 생성

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

2. 배열 vs. 연결리스트

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

3. 연산 정의

• 특정 원소 참조 (k번째)
• 리스트 순회
• 길이 얻어내기
• 원소 삽입
• 원소 삭제
• 두 리스트 합치기

1) 특정 원소 참조 (k번째)

# LinkedList 클래스의 함수
def getAt(self, pos):
    if pos <= 0 or pos > self.nodeCount:
        return None
    i = 1
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1
    return curr

2) 리스트 순회

def traverse(self):
    lst = []
    now = self.head
    while now != None:
        lst.append(now.data)
        now = now.next
    return lst

3) 길이 얻어내기

• self.nodeCount 출력

4) 원소 삽입

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:
        # 맨 끝에 삽입할 경우 -> tail이 prev
        if pos == self.nodeCount + 1:  
            prev = self.tail
        # 나머지 경우 -> getAt 메서드 사용
        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

• 원소 삽입 복잡도
  • 맨 앞에 삽입하는 경우: $O(1)$
  • 중간에 삽입하는 경우: $O(n)$
  • 맨 끝에 삽입하는 경우: $O(1)$

5) 원소 삭제

• 주의사항
  • 삭제하려는 노드가 맨 앞의 것일 때
    • prev 없음
    • head 조정 필요
  • 리스트 맨 끝의 노드 삭제할 때
    • tail 조정 필요
    • prev를 찾을 방법이 없기 때문에 tail로 한 번에 처리할 수 없음
  • 유일한 노드를 삭제할 때?
• 원소 삽입 복잡도
  • 맨 앞에 삽입하는 경우: $O(1)$
  • 중간에 삽입하는 경우: $O(n)$
  • 맨 끝에 삽입하는 경우: $O(n)$

def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        curr = self.getAt(pos)
        
        if pos == 1:
            if self.nodeCount == 1:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next

        else:
            prev = self.getAt(pos-1)
            if pos == self.nodeCount:
                prev.next = None
                self.tail = prev
            else:
                prev.next = curr.next
        
        self.nodeCount -= 1
        return curr.data

6) 두 리스트의 연결

def concat(self, L):

4. 연결리스트 클래스 코드

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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr is not None:
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
            curr = curr.next
        return s


    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 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 getLength(self):
        return self.nodeCount


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


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

5. 조금 변형된 연결리스트

• 맨 앞에 dummy node 추가
  • 데이터가 없는 노드
  • 기존 연결리스트는 맨 앞에 원소를 삽입하거나 삭제하는 연산을 지정하기 애매함
• 새로운 메서드 추가
  • reverse(self)
  • insertAfter(prev, newNode)
  • popAfter(prev)

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


class LinkedList:
	def __init__(self):
		self.nodeCount = 0
        # dummy node
		self.head = Node(None)
		self.tail = None
		self.head.next = self.tail


	def __repr__(self):
		if self.nodeCount == 0:
			return 'LinkedList: empty'

		s = ''
		curr = self.head
		while curr.next:
			curr = curr.next
			s += repr(curr.data)
			if curr.next is not None:
				s += ' -> '
		return s


	def getLength(self):
		return self.nodeCount


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

    def reverse(self):
        result = []
        if self.nodeCount == 0:
            return 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

		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):   
        curr = prev.next
        prev.next = curr.next
        if curr.next is None:
            self.tail = prev
        self.nodeCount -= 1
        return curr.data
        

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        if pos == 1 and pos != self.nodeCount:
            self.head = pos.next
        else:
            prev = self.getAt(pos-1)
        return self.popAfter(prev)                                                

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

6. Doubly Linked List

• 한 쪽으로만 링크를 연결하지 말고, 양쪽으로 연결하자!
• 앞으로도 (next node) 뒤로도 (previous node) 진행 가능

• 노드에 prev 추가

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

• 리스트 처음과 끝에 dummy node 생성
  • -> 데이터를 담고 있는 노드들은 모두 같은 모양
  • 코드 작성이 편안해짐

class DoublyLinkedList:
    def __init__(self, item):
        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

7. 연산 정의

1) 리스트 순회

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

역순회

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

2) 원소 삽입

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

3) 특정 원소 얻어내기

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

    # pos가 리스트의 뒤쪽에 있을 경우
    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

8. 스택

• 자료를 보관할 수 있는 (선형) 구조
• 후입선출 (LIFO)
  • 밀어 넣는: push 연산
  • 같은 쪽에서 뽑아 꺼내는: pop 연산

9. 스택의 추상적 자료구조 구현

1) 배열을 이용하여 구현

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]

2) 연결리스트를 이용하여 구현

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

10. 스택 라이브러리

from pythonds.basic.stack import Stack
S = Stack()

dir(S)
# ['__doc__', '__init__', '__module__', 'isEmpty', 'items', 'peek', 'pop', 'push', ...]

11. 중위 표기법과 후위 표기법

• 중위 표기법: 연산자가 피연산자들의 사이에 위치
  • (A + B) * (C + D)
  •       1     3      2
• 후위 표기법: 연산자가 피연산자들의 뒤에 위치
  • 연산자 나온 순서대로 계산 가능

  • 괄호 필요 없음

  • A B + C D + *
  •        1         2 3

중위 표현식 -> 후위 표현식

[A * B + C] -> [A B * C +]

[A + B * C] -> [A B C * +]

12. 알고리즘

괄호가 없는 경우

• 피연산자 -> 그대로 후위 표현식에 적음
• 연산자 -> 스택에 넣음
  • 스택이 비어있지 않으면 해당 연산자와 스택의 꼭대기 원소와 우선순위 비교
  • 스택에 있던 원소가 우선순위 높거나 같은 경우
    • pop -> 후위 표현식에 적음
    • 나머지 연산자는 push
  • 표현식에서 나온 연산자가 스택의 꼭대기 원소보다 우선순위 높은 경우
    • 그대로 push
• 수식의 끝 -> 스택에서 연산자 pop해서 후위 표현식에 적음

괄호가 있는 경우

• 여는 괄호는 스택에 push
• 닫는 괄호를 만나면, 여는 괄호가 나올 때까지 pop
• 연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록
  • 여는 괄호의 우선순위는 가장 낮게 설정

13. 알고리즘 설계

1) 연산자 우선순위 설정

prec = {
    '*':3, '/':3,
    '+':2, '-':2,
    '(':1
}

2) 연산

• 왼쪽부터 한글자씩 읽음
• 피연산자이면 그냥 출력
• ’(‘이면 스택에 push
• ’)’이면 ‘(‘이 나올 때까지 스택에서 pop, 출력
• 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력
  • 그리고 이 연산자는 스택에 push
• 스택에 남아있는 연산자는 모두 pop, 출력

14. 후위 표기 수식 계산

• 후위 표현식을 왼쪽부터 한 글자씩 읽어서
• 피연산자이면 스택에 push
• 연산자를 만나면 스택에서 pop (1) , 또 pop (2)
  • (2) 연산 (1) 계산 -> 이 결과를 스택에 push
  • 뺄셈 / 나눗셈 -> 피연산자 순서 주의!
• 수식의 끝에 도달하면 스택에서 pop => 계산 결과

# 문자열로 들어온 숫자를 수와 연산자로 분리하여 list로
def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False

    for c in exprStr:
        if c = ' ':
            continue
        if c in '0123456789':   # 피연산자
            val = val * 10 + int(c)
            valProcessing = True    # 10진수 처리중
        else:    
            if valProcessing:   # 10진수 표현이 끝난 것 -> tokens에 추가
                tokens.append(val)
                val = 0
            valProcessing = False   # 10진수 처리중 X
            tokens.append(c)  # 연산자 tokens에 추가
    if valProcessing:
        tokens.append(val)
    
    return tokens

# 중위표기 -> 후위표기
from stacks import ArrayStack as Stack

def infixToPostfix(tokenList):
    prec = {
        '*':3,
        '/':3, 
        '+':2,
        '=':2,
        '(':1
    }

    opStack = Stack()
    postfixList = []

    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        else:
            if opStack.isEmpty():
                opStack.push(token)
            else:
                while prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
                    if opStack.isEmpty():
                        break
                opStack.push(token)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList

# 후위 표현 수식 계산
from stacks import ArrayStack as Stack

def postfixEval(tokenList):
    valStack = Stack()

    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
        elif token == '*':
            a = valStack.pop()
            b = valStack.pop()
            valStack.push(b*a)
        elif token == '/':
            a = valStack.pop()
            b = valStack.pop()
            valStack.push(b/a)
        elif token == '+':
            a = valStack.pop()
            b = valStack.pop()
            valStack.push(b+a)
        elif token == '-':
            a = valStack.pop()
            b = valStack.pop()
            valStack.push(b-a)
    return valStack.pop()

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val