연결 리스트
연속된 공간에 데이터를 저장하는 방식인 리스트와는 다르게 연결 리스트(linked list)는 연속적이지 않는 공간에 데이터를 줄줄이 엮어서 저장한다. 연결 리스트는 일반적인 리스트보다 특정 원소의 삽입/ 삭제가 수월하다는 장점이 있지만, 특정 원소를 탐색하는 시간이 길고 요구되는 메모리 공간이 더 크다는 단점이 있다. 따라서 각각의 상황이 요구하는 자료구조를 제대로 파악해서 적절하게 사용하는 능력을 키우는것이 중요하다.
연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.
- 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조
- 이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원소 주소를 들고 있는 구조
c++에서 제공하는 STL에 있는 연결리스트는 이중 연결 리스트 구조이다. - 원형 연결 리스트 - 단일 연결 리스트/ 이중 연결 리스트 구조에서 끝이 처음과 연결되어있는 구조
단일 연결 리스트 구현 코드
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):
if prev.next is None:
return None
else:
curr = prev.next
if curr.next is None:
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
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리스트 각각의 노드가 지정하는 다음 노드들을 적절히 변경시켜가며 삽입/ 삭제/ 탐색 등을 해나가는 코드이다.
head, tail, curr, next, prev들이 각각 어떤 노드를 뜻하는 것인지 잘 이해하면 쉽게 구현할 수 있다.
단일 연결 리스트를 짜다보면 next 이외에도 이전 노드를 참조해야하는 경우과 꽤 있다는 것을 알 수 있다. 하지만 단일 연결 리스트의 구조상 이전 노드를 참조하기 위해서는 연결 리스트의 처음부터 원하는 위치까지 쭉 타고 들어가야되서 번거롭다. 이러한 경우에 사용할 수 있는것이 이중 연결 리스트이다. 이중 연결 리스트는 다음 노드 뿐만 아니라 이전 노드의 위치까지 가지고 있어서 쉬운 참조가 가능해진다.
이중 연결 리스트 구현 코드
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 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 insertBefore(self, next, newNode):
prev = next.prev
newNode.prev = prev
prev.next = newNode
newNode.next = next
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
next = curr.next
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popBefore(self, next):
curr = next.prev
prev = curr.prev
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos<1 or pos>self.nodeCount:
raise IndexError
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
def concat(self, L):
if L.nodeCount == 0:
return True
if self.nodeCount == 0:
self.head.next = L.head.next
if L.head.next:
L.head.next.prev = self.head
self.tail = L.tail
self.nodeCount += L.nodeCount
return True
prev = self.tail.prev
next = L.head.next
prev.next = next
next.prev = prev
self.nodeCount += L.nodeCount
self.tail = L.tail
return True단일 연결 리스트와 양방향 연결 리스트 구현은 전체적인 틀이 매우 비슷하다. 단일 연결 리스트를 혼자 이해하고 구현할 수 있다면 이중 연결 리스트 역시 쉽게 이해 가능할것이다.
스택
스택이란 후입선출(LIFO) 방식의 자료 구조이다. 스택의 대표적인 연산으로는 값을 집어넣는 Push, 값을 추출하는 Pop 연산이 있다.
스택은 다른 알고리즘을 풀 때 자주 사용되는 자료 구조이므로 확실히 이해하고 넘어가는게 중요하다. 스택은 오로지 최상단 원소에 대한 접근 문제만 나온다. 만일 중간 원소 접근을 요구하면 스택이 아닌 다른 풀이를 적용!
스택은 선형 배열을 이용해 구현하는 방법과 연결 리스트를 이용해 구현하는 방법 두가지가 있으며 아래가 해당 코드이다.
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
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
- size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
- isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)
- push(x): 데이터 원소 x 를 스택에 추가
- pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
- peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음
스택의 응용 - 후위 표기법
스택의 활용 중 대표적인 예시는 중위 표기법을 후위 표기법으로 바꾸는 것이다.
- 중위 표기법 : 연산자가 피연산자들의 사이에 위치 => (A+B) * (C+D)
- 후위 표기법 : 연산자가 피연산자들의 뒤에 위치 => AB + CD + *
중위 표현식을 돌면서 피연산자를 만날 경우, 후위 표현식을 위한 리스트에 넣는다. 연산자를 만날 경우, 스택에 삽입한다.
만약 스택에 이미 들어있는 연산자가 있는 경우엔 두 연산자의 우선순위를 비교한다. 스택에 있는 원소가 우선순위가 높을땐 해당 원소를 pop한 후 연산자를 push하며, push할 원소가 우선순위가 높을땐 그냥 push를 한다. 또한 우선순위가 같을 때에는 스택에 있는것을 pop한 후에 push를 하면 된다.
우리는 괄호가 있을때 역시 고려해야한다. 여는 괄호는 push, 닫는 괄호가 나오면 짝을 이루는 괄호가 나올때까지 pop을 하면된다. 이때 괄호의 우선순위를 제일 높게 설정해야 함을 주의하자.
우선순위 => 여는 괄호 > 곱셈, 나눗셈 > 덧셈, 뺄셈
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer = ''
for i in S:
if i in "ABCDEFGHIZKLMLOPQRSTUVWXYZ":
answer+=i
elif i == '(':
opStack.push(i)
elif i == ')':
while opStack.peek() != '(' and not opStack.isEmpty():
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'알고리즘' 카테고리의 다른 글
| [자료구조] 해시 & 그리디 (0) | 2024.03.28 |
|---|---|
| [자료구조] 이진 트리 & 힙 (0) | 2024.03.27 |
| 백준 #1912 <연속합> 파이썬 (0) | 2024.03.12 |
| 백준 #1699 <제곱수의 합> (0) | 2024.03.09 |
| 백준 #1463 <1로 만들기> (0) | 2024.03.08 |