연결 리스트 (Linked List)
추상적 자료 구조
Node내 데이터는 다른 구조로 이루어질 수 있음.
head, tail, node 수 가 기본 속성.
| 배열 | 연결리스트 | |
|---|---|---|
| 저장공간 | 연속위치 | 임의로 위치 |
| 특정원소 | 매우간편 | 선형탐색과 유사 |
| 시간복잡도 | O(1) | O(n) |
원소 순회
def traverse(self):
curr = self.head
result = []
if curr is None:
return result
while curr is not None:
result.append(curr.data)
curr = curr.next
return result연결 리스트 원소 삽입의 복잡도
맨 앞: O(1)
중간: O(n)
맨 끝: O(1)
연결 리스트 원소 삭제의 복잡도
맨 앞: O(1)
중간: O(n)
맨 끝: O(n)
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
if pos == 1:
curr = self.head
if curr.next is None:
self.head = None
self.tail = None
else:
self.head = curr.next
else:
prev = self.getAt(pos-1)
curr = prev.next
if pos == self.nodeCount:
prev.next = None
self.tail = prev
else:
prev.next = curr.next
curr.next = None
self.nodeCount -= 1
return curr.data 연결 리스트가 힘을 발휘할 때
ex> 아이폰 실행 중 어플 삭제할 때.
삽입과 삭제가 유연하다는 것이 큰 장점
두 리스트 합치기
def concat(self, L):
L.head.next.prev = self.tail.prev
self.tail.prev.next = L.head.next
self.tail = L.tail
self.nodeCount += L.nodeCount 단점: 연결리스트의 아쉬운 점은 거꾸로 가지 못해서 나온 것이 -> 양방향 연결 리스트(Doubly Linked Lists)
양방향 연결 리스트(Doubly Linked Lists)
한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
-> 앞으로도 뒤로도 진행 가능
- 리스트의 처음과 끝에 dummy node를 두자
-> 데이터를 담고 있는 node들은 모두 같은 모양
원소의 삽입
특정 원소 얻어내기
def insertBefore(self, next, newNode):
prev = next.prev
prev.next = newNode
next.prev = newNode
newNode.next = next
newNode.prev = prev
self.nodeCount += 1
return True스택(Stack)
자료(data element)를 보관할 수 있는 선형 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(PUSH) 꺼낼 때에는 같은 쪽에서 뽑아 꺼냄.
후입선출(LIFO: Last In First Out) 구조
스택의 추상적 자료구조 구현
- 배열을 이용: Python 리스트와 메서드들을 이용
- 연결 리스트를 이용: 양방향 연결 리스트 이용
연산의 정의
size(): 현재 스택에 들어있는 데이터 원소의 수를 구함
isEmpty(): 현재 스택이 비어 있는지를 판단
push(x): 데이터 원소 x를 스택에 추가
pop(): 스택의 맨 위에 저장된 데이터 원소를 제거 (+반환)
peek(): 스택의 맨 위에 저장된 데이터 원소를 반환 (제거X)
예시: 수식의 괄호 유효성 검사
올바른 수식: (A+B)
올바르지 않은 수식: ((A+B)
중위 표기법과 후위 표기법
중위 표기법 (infix notation) - 연산자가 피연산자들의 사이에 위치
(A + B) * (C + D)
후위 표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치
A B + C D + *
중위 표현식 -> 후위 표현식
알고리즘의 설계
- 연산자의 우선순위 설정
- 중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 그냥 출력
- '('이면 스택에 push
- ')'이면 '('이 나올 때까지 스택에서 pop
- 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
- 그리고 이 연산자는 스택에 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]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer = ''
for letter in S:
if letter == ' ':
continue
if letter not in (str(prec.keys())+')'):
answer += letter
else:
if letter == '(':
opStack.push(letter)
elif letter == ')':
while True:
c = opStack.pop()
if c == '(':
break
answer += c
else:
priority = prec.get(letter)
if not opStack.isEmpty():
while priority <= prec.get(opStack.peek()):
answer += opStack.pop()
if opStack.isEmpty():
break
opStack.push(letter)
while not opStack.isEmpty():
answer += opStack.pop()
return answer후위 표기식의 계산
알고리즘의 설계
- 후위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 스택에 push
- 연산자를 만나면 스택에서 pop -> (1), 또 pop -> (2)
- (2) (연산) (1)을 계산, 결과 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 letter in tokenList:
if letter not in list(prec.keys()) + [')']:
postfixList.append(letter)
else:
if letter == '(':
opStack.push(letter)
elif letter == ')':
while True:
c = opStack.pop()
if c == '(':
break
postfixList.append(c)
else:
priority = prec.get(letter)
if not opStack.isEmpty():
while priority <= prec.get(opStack.peek()):
postfixList.append(opStack.pop())
if opStack.isEmpty():
break
opStack.push(letter)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return postfixList
def operate(n1, n2, op):
if op == '+':
return n1+n2
elif op == '-':
return n1-n2
elif op == '*':
return n1*n2
elif op == '/':
return n1/n2
def postfixEval(tokenList):
letterStack = ArrayStack()
for letter in tokenList:
if type(letter) == type(0): # 숫자이면
letterStack.push(letter)
else:
a = letterStack.pop()
b = letterStack.pop()
letterStack.push(operate(b, a, letter))
return letterStack.pop()
def solution(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val'데이터엔지니어링' 카테고리의 다른 글
| [2주차] 파이썬으로 웹다루기 (1) (0) | 2024.04.01 |
|---|---|
| [1주차] 자료구조 / 알고리즘 (5) (0) | 2024.03.29 |
| [1주차] 자료구조 / 알고리즘 (4) (0) | 2024.03.28 |
| [1주차] 자료구조 / 알고리즘 (3) (0) | 2024.03.27 |
| [1주차] 자료구조 / 알고리즘 (1) (0) | 2024.03.25 |