[데브코스] TIL 2일차

dev course - DE/TIL

[데브코스] TIL 2일차

nani-jin 2024. 3. 26. 14:19

*추상적 자료구조
- 구현 방법은 명시하지 않지만, 데이터와 기능을 추상적으로 보여주는 자료구조

연결 리스트(Linked Lists)
노드(첫번째는 헤드)는 데이터와 링크로 이루어져 있음

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

노드를 클래스로 구현하면

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

연결리스트의 연산
1) 특정 원소 참조(k번째)
2) 리스트 순회
3) 길이 얻어내기
4) 원소 삽입
5) 원소 삭제
6) 두 리스트 합치기

## 특정 원소 참조(k번째)
def getAt(self,pos):
    if pos <= or pos > self.nodeCount:
    	return None
        
    i = 1
    curr = self.head
    
    while i < pos:
    	curr = curr.next
        i += 1
    return curr
    

## 리스트 순회
def traverse(self):
    answer = []
    
    curr = self.head
    while curr:
    	answer.append(curr.data)
        curr = curr.next
    return answer
    
    
## 원소 삽입
# 삽입하려는 위치의 전 노드를 prev로.
# 먼저 삽입하려는 새로운 노드의 next를 prev의 next로
# prev의 next를 삽입한 새로운 노드로
# node가 1개 늘어났으니 nodeCount += 1

# 코너 케이스 1) 삽입하려는 위치가 리스트 맨 앞일 때. prev 없음. head 조정 필요
# 코너 케이스 2) 삽입하려는 위치가 리스트 맨 끝일 때. tail 조정 필요

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
    
    
## 원소 삭제
# 코너 케이스 1) 삭제하려는 node가 맨 앞의 것일 때. prev 없음. head 조정 필요
# 코너 케이스 2) 리스트 맨 끝의 node를 삭제할 때. tail 조정 필요
# 코너 케이스 3) 유일한 노드를 삭제할 때

def popAt(self, pos):
    del_node = self.getAt(pos)
        
    if pos < 1 or pos > self.nodeCount:
        raise IndexError
        
    if pos == 1: # 삭제하려는 노드가 헤드 노드일때
        if self.nodeCount == 1: # 노드 1개일때
            self.head = None
            self.tail = None
            self.nodeCount = 0
                
        else: # 노드 2개 이상일때
            self.head = self.head.next
            self.nodeCount -= 1
                
        return del_node.data
        
    else: # 헤드노드 아닐때
        prev = self.getAt(pos-1)
        if pos == self.nodeCount: # tail 노드일때
            prev.next = None
            self.tail = prev
        else: # tail 노드 아닐때
            prev.next = del_node.next
                
        self.nodeCount -= 1
        
        return del_node.data
       
       
 ## 두 연결 리스트 합치기
 def concat(self,L):
    self.tail.next = L.head
    if L.tail:
    	self.tail = L.tail
    self.nodeCount += L.nodeCount

연결 리스트가 힘을 발휘할 때?
- 순서 있는 것을 활용할 때
- 삽입과 삭제가 유연하다!
→ 그런데 지금까지 본 getAt은 처음부터 쭉 원하는 위치까지 따라가야 알 수 있었잖아?
→ 삭제할 노드의 앞 노드를 알려주는 새로운 메서드를 통해 해결.
→ insertAfter(prev,newNode)와 popAfter(prev)
→ 맨 앞의 노드는 어떻게?
→ 맨 앞에 dummy node를 추가함

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

# k번째 원소 얻어내기
	def getAt(self,pos):
    	if pos < 1 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
        
        if prev.next == None:
        	return None
        
        if curr.next == None:
        	if self.nodeCount == 1:
            	self.tail = None
            else:
            	self.tail = prev
        
        prev.next = curr.next
        self.nodeCount -= 1
        
        return curr.data
            
    
    def popAt(self,pos):
    	if pos < 1 or pos > self.nodeCount:
        	raise IndexError
        
        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

양방향 연결 리스트(Doubly Linked Lists)
한 쪽으로만 링크를 연결하지 말고, 양쪽으로! →앞으로도(다음 노드) 뒤로도(이전 노드) 진행 가능

# 연결 리스트에 prev 참조도 가능하니, Node 구조를 확장해야 한다
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
        
        
    ## 리스트 순회
    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.apepnd(curr.data)
        return result
        
    ## 원소 삽입
    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 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 insertAt(self,pos,newNode):
    	if pos < 1 or pos > self.nodeCount + 1:
        	return False
            
        prev = self.getAt(pos-1)
        return self.insertAfter(prev,newNode)

스택(Stack)

자료를 보관할 수 있는 (선형) 구조. 단, 넣고 꺼낼 때 한쪽에서만 이뤄질 수 있는 LIFO(Last-in First-out)

기능
1) push
2) pop
스택에서 발생하는 오류
1) stack underflow : 비어있는 스택에서 데이터 원소를 꺼내려 할 때
2) stack overflow : 꽉 찬 스택에 데이터 원소를 넣으려 할 때
스택의 추상적 자료구조 구현
1) 배열을 이용해 구현 : python 리스트와 메서드 이용
2) 연결 리스트를 이용해 구현 : 양방향 연결 리스트 이용
연산
1) size() : 현재 스택에 들어 있는 데이터 원소의 수
2) isEmpty() : 현재 스택이 비어 있는지를 판단
3) push(x) : 데이터 원소 x를 스택에 추가
4) pop() : 스택의 맨 위에 저장된 데이터 원소를 제거(&반환)
5) peek() : 스택의 맨 위에 저장된 데이터 원소를 반환(제거하지 않음)

## 배열로 구현
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]
        
        
## 양방향 연결 리스트로 구현
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

수식의 후위 표기법
- 연산자가 피연산자들의 뒤에 위치함

1) 연산자의 우선순위 설정
prec = {'*' : 3, '/' : 3, '+' : 2, '-' : 2, '(' : 1}
2) 중위 표현식을 왼쪽부터 한 글자씩 읽어서
피연산자면 → 출력
'(' → 스택에 push
')' → '('이 나올 때까지 스택에서 pop, 출력
연산자면 → 스택에서 이보다 높(거나 같)은 우선순위인 것들을 pop, 출력. 그리고 이 연산자는 스택에 push
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()
    answer = ''
    
    for i in S:
        if i.isalpha(): # 피연산자
            answer += i
        elif i == '(':
            opStack.push(i)
        elif i == ')':
            while not opStack.isEmpty() and opStack.peek() != '(':
                answer += opStack.pop()
            opStack.pop()
        else: # 연산자
            while not opStack.isEmpty() and prec[i] <= prec[opStack.peek()]:
                answer += opStack.pop()
            opStack.push(i)
    
    while not opStack.isEmpty():
        answer += opStack.pop()
    return answer

수식의 후위 표기 계산
- 후위 표현식을 왼쪽부터 한 글자씩 읽어서
피연산자면 → 스택에 push
연산자면 → 스택에서 (1) pop (2) pop (3) 연산 (4) 연산 결과 다시 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 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: # 연산자면
            while not opStack.isEmpty() and prec[token] <= prec[opStack.peek()]:
                postfixList.append(opStack.pop())
            opStack.push(token)
            
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList

# 후위 표기 계산
def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        if type(token) is int: # 피연산자
            valStack.push(token)
    
        elif token == '*':
            v1 = valStack.pop()
            v2 = valStack.pop()
            valStack.push(v2*v1)
        
        elif token == '-':
            v1 = valStack.pop()
            v2 = valStack.pop()
            valStack.push(v2-v1)

        elif token == '+':
            v1 = valStack.pop()
            v2 = valStack.pop()
            valStack.push(v2+v1)
            
        elif token == '/':
            v1 = valStack.pop()
            v2 = valStack.pop()
            valStack.push(int(v2/v1))
    
    return valStack.pop()
        


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