2023/10/17

anso·2023년 10월 17일
알고리즘자료구조
0

TIL

목록 보기
2/20
post-thumbnail

연결 리스트 Linked Lists

노드가 한 방향으로 연결되어 있는 형태

  • head, tail, nodeCount로 구성
    head : 제일 앞 노드
    tail : 제일 뒷 노드
    nodeCount : 노드 개수

  • 장점 : 데이터를 자유롭게 삽입하고 삭제 가능 → Dummy Node(빈 노드) 사용

class LinkedList:
	def __init__(self):
    self.nodeCount = 0
    self.head = Node(None)  # dummy node
    self.tail = None
    self.head.next = self.tail
  • 단점 : 선형 배열에 비해 저장공간(메모리) 소요가 큼
배열연결리스트
저장공간연속한 위치임의의 위치
특정 원소 지칭매우 간편선형탐색과 유사
시간 복잡도O(1)O(n)

연산

  • 특정 원소 참조(k번째)
def getAt(self, pos):
	if pos < 0 or pos > self.nodeCount:
        return None

    i = 0	# 시작 노드 = dummy node
    curr = self.head

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

    return curr
  • 리스트 순회 traversal
def traverse(self):
	result = []
    curr = self.head
    while curr.next:
    	curr = curr.next
        result.append(curr.data)
    
    return result
  • 두 리스트 합치기 concatenation
def concat(self, L):
	self.tail.next = L.head.next
    
    if L.tail:
    	self.tail = L.tail
        
    self.nodeCount += L.nodeCount
  • 원소 삽입 insertion
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 getLength(self):
		return self.nodeCount
  • 원소 삭제 deletion

양방향 연결 리스트 Doubly Linked Lists

노드가 양방향으로 연결되어 있는 형태

  • 기존의 연결 리스트와 다르게 노드의 구조확장 필요
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

연산

  • 리스트 순회 traversal
 def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
  • 원소 삽입 insertion
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)
  • 리스트 병합 concatenation
def concat(self, L):
    self.tail = self.tail.prev
    L.head = L.head.next

    self.tail.next = L.head
    L.head.prev = self.tail

    self.tail = L.tail

    self.nodeCount += L.nodeCount
  • 원소 삭제 deletion

스택 Stacks

추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료구조

  • 후입선출(LIFO) 구조

구현 방법

  • 배열 : 리스트 메서드 이용
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

연산

  • size( ) : 현재 스택에 들어있는 데이터의 원소의 수
  • isEmpty( ) : 현재 스택이 비어있는지 판단
  • push(x) : 데이터 원소 x 추가
  • pop( ) : 스택에 가장 나중에 저장된 데이터 원소 제거 and 반환
  • peek( ) : 스택에 가장 나중에 저장된 데이터 원소 반환

수식의 후위 표기법 Postfix Notation

연산자가 피연산자들의 뒤에 위치
(A + B) * (C + D) → A B + C D + *
A + B * C → A B C * +

알고리즘 설계

  1. 연산자의 우선순위 결정
prec = {
		'*' : 3, '/' : 3,
        '+' : 2, '-' : 2,
        '(' : 1
}
  1. 왼쪽부터 한 글자씩 읽기
  2. 열린 괄호는 push, 닫힌 괄호가 나올 때까지 pop
  3. 수식을 끝까지 확인한 후 스택에 남은 연산자 모두 pop

중위표현 수식 → 후위표현 수식

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]

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

def solution(S):
    opstack = ArrayStack()
        
    ans = ""
    
    for s in S:        
        if s == "(":
            opstack.push(s)
            
        elif s in prec:
            while not opstack.isEmpty() and prec[s] <= prec[opstack.peek()]:
                ans += opstack.pop()
            opstack.push(s)

        elif s == ")":
            while opstack.peek() != "(":
                ans += opstack.pop()
            
            opstack.pop()
            
        else:
            ans += s
            
    while not opstack.isEmpty():
        ans += opstack.pop()
        
    return ans

후위 표기 수식 계산

알고리즘 설계

  1. 수식을 왼쪽부터 시작해서 오른쪽으로 차례대로 읽기
  2. 피연산자는 push, 연산자는 pop
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]


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
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens


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

    opStack = ArrayStack()
    postfixList = []
    
    for s in tokenList:        
        if s == "(":
            opStack.push(s)
            
        elif s in prec:
            while not opStack.isEmpty() and prec[s] <= prec[opStack.peek()]:
                postfixList.append(opStack.pop())
            opStack.push(s)

        elif s == ")":
            while opStack.peek() != "(":
                postfixList.append(opStack.pop())
            
            opStack.pop()
            
        else:
            postfixList.append(s)
            
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
        
    return postfixList


def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for t in tokenList:
        if type(t) is int:
            valStack.push(t)
        
        else:
            if t == "*":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b * a)
            elif t == "/":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b / a)
            elif t == "+":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b + a)
            elif t == "-":
                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
profile
anso
이전 포스트

2023/10/16

다음 포스트

2023/10/18 (1)

0개의 댓글