1주차 화요일, 2일차 Today I Learned
자료구조와 알고리즘 (2)
: 연결 리스트, 스택, 후위 표현/표기
✏️ 학습 내용
1. 연결 리스트
- 종류 : 단일, 양방향(이중)
- 연산 : 특정 원소 참조, 리스트 순회, 길이 얻어내기, 원소 삽입, 원소 삭제, 리스트 합치기
- dummy node 처리하기
2. 스택
- 정의와 동작(후입선출)
- 연산(push, pop)과 에러(스택 언더플로우/오버플로우)
- 추상적 자료구조 표현와 스택을 응용한 후위 표기법
1. 연결 리스트 (Linked Lists)
- (정의) 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
비슷한 듯 다른
연결 리스트와 선형 배열의 차이점은 데이터 원소들을 늘어놓는 방식이 다르다는 것이다. 선형 배열이 번호가 붙여진 칸에 원소들을 채워넣는 방식이라고 하면, 연결 리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식이다.
| 배열 | 연결 리스트 | |
| 데이터 원소 | 번호가 붙여진 칸에 원소들 채워넣는 방식 | 각 원소들을 줄줄이 엮어서 관리하는 방식 |
| 저장 공간 | 연속한 위치 | 임의의 위치 |
| 특정 원소 지칭 | 매우 간편 | 선형탐색과 유사 |
| 복잡도 | O(1) | O(n) |
연결 리스트 장단점
장점 원소들이 링크라고 부르는 고리로 연결되어 있으므로, 가운데서 끊어 원소를 삽입하거나 삭제하는 것이 쉽다(빠르다).
단점 데이터 구조 표현에 소요되는 저장 공간 소요가 크고, 무엇보다 'k번째의 원소'를 찾아가는 데에는 시간이 오래 걸린다.
✔️ 추상적 자료 구조(Abstract data structures)인 단방향 연결 리스트 (Singly linked list)의 연산들
추상적 자료 구조란?
자료 자체의 형태와 그 자료에 관계된 연산들을 수학적으로만 정의한 것 (집합, 리스트, 스택, 큐, 트리 등)
- Data & A set of operations
자료 구조 정의
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이전 : prev : pos - 1
현재 : curr : pos
다음 : next : pos + 1
➀ 특정 원소 참조 (k번째)
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
➁ 리스트 순회 (List traversal)
➂ 길이 얻어내기
➃ 원소 삽입 (insertion)
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: # (2) 조정 부분
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 Truepos가 가리키는 위치에 (범위 : 1 <= pos <= nodeCount + 1) newNode를 삽입하고 성공/실패에 따라 True or False를 리턴한다. ➀ 원래 pos가 가리키는 위치를 구하고, ➁ 이에 newNode를 삽입한 후에 ➂ nodeCount에 1씩 더한다.
단, 코드 구현 시 주의해야 하는 사항이 있는데, (1) 삽입하려는 위치가 리스트 맨 앞일 때에는 prev가 없어서 Head 조정이 필요하다. 그리고 (2) 삽입하려는 위치가 리스트 맨 끝일 때에는 Tail 조정이 필요하다. 이 때 prev == tail과 같으며, 맨 앞에서부터 찾아갈 필요가 없다. 빈 리스트에 삽입하려고 할 때에는 이 두 조건에 따라 자동으로 처리된다.
연결 리스트 원소 삽입의 복잡도 비교
- 맨 앞에 삽입하는 경우 : O(1)
- 중간에 삽입하는 경우 : O(n)
- 맨 끝에 삽입하는 경우 : O(1)
➄ 원소 삭제 (deletion)
pos가 가리키는 위치에 (범위 : 1 <= pos <= nodeCount + 1) 해당 node를 삭제하고 그 node의 데이터를 리턴한다.
단, 코드 구현 시 주의해야 하는 사항이 있는데, (1) 삭제하려는 node가 맨 앞일 때에는 prev가 없어서 Head 조정이 필요하다. 그리고 (2) 리스트 맨 끝의 node를 삭제하려고 할 때에는 Tail 조정이 필요하다. 이 경우는 curr=tail, pos == nodeCount가 되는데, prev를 찾을 방법이 없으므로 한 번에 처리할 수 없고, 앞에서부터 찾아와야 한다.
또한 (3) 유일한 노드를 삭제할 때에는 다른 조건이 필요하다.
연결 리스트 원소 삭제의 복잡도 비교
- 맨 앞에 삽입하는 경우 : O(1)
- 중간에 삽입하는 경우 : O(n)
- 맨 끝에 삽입하는 경우 : O(n)
➅ 두 리스트 합치기 (concatenation)
def concat(self, L) :
self.tail.next = L.head
if L.tail :
self.tail = L.tail
self.nodeCount += L.nodeCount연결 리스트 self의 뒤에 또 다른 연결 리스트인 L을 이어 붙이는 방법이다. (L1 + L2) 그러기 위해선 ➀ self.tail.next = L2.head, 즉 현재 리스트(L1)의 맨 끝(tail) 다음(next)이 다음 리스트(L2)의 맨 앞(head)로 연결되어야 하고, ➁ self.tail = L2.tail, 즉 현재 리스트(L1)의 맨 끝(tail)을 다음 리스트(L2)dml 맨 끝(tail)으로 이어붙여야 한다. tail을 옮겨야 하므로 L1의 tail이 맨 끝으로 가야 하기 때문이다.
다만, L2가 빈 값일 경우를 고려하여 작성하여야 한다.
✔️ 연결 리스트의 이용
연결 리스트는 언제 힘을 발휘하는 것일까?
실생활에 엮어서 생각해보면 쉬울 것 같으니 예시를 한 번 찾아보자. 가장 대표적으로 '아이폰에서 최근 실행 앱을 닫을 때' 활용된다. 아이폰 화면 밑에서부터 위로 쓸어올리면 최근 실행한 앱 리스트가 나오게 되는데, 이 때 원하는 어플을 화면 위로 쓸어올리면 강제 종료가 된다. 이것이 연결 리스트에서 삭제를 할 때의 예시가 된다.
이처럼 연결 리스트의 최대 장점은 삽입과 삭제가 유연하다는 것이다. 쉽고, 빠르다. 이를 최대한 응용하기 위해 insertAfter, popAfter 메서드를 추가하려고 한다. 맨 앞에 dummy node를 추가한 형태로 맨 앞에 삽입/삭제를 하고자 하는 경우를 에러없이 해결할 수 있다.
class LinkedList :
def __init__(self) :
self.nodeCount = 0
self.head = Node(None)
self.tail = None
self.head.next = self.tail
이에 따라 하위 메서드들의 코드가 조금씩 바뀌어야 한다. 예를 들어, 원소 삽입 코드는 다음과 같다.
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)
insertAfter()를 호출하여 insertAt()을 구현할 수 있다. ➀ pos 범위가 올바른 조건 내에 들어있는가를 확인하고, ➁ pos == 1인 경우, head 뒤에 새 node를 삽입한다. ➂ pos == nodeCount + 1인 경우에는 prev = tail, ➃ 그렇지 않은 경우에는 prev = getAt()으로 한다.
이처럼 리스트 맨 앞에 dummy node를 추가하는 것만으로도 코드가 좀 더 깔끔해질 수 있다.
✔️ 양방향 연결 리스트 (이중 연결 리스트, Doubly linked list)
- 모든 연결이 양방향으로 이루어져 있는 연결 리스트 (인접한 두 개의 노드들이 서로 앞뒤로 연결)
- (단점) 링크를 나타내기 위한 메모리 사용량이 늘어나고, 연산 시 앞/뒤 링크를 모두 조정해야 해서 코딩을 더 해야한다.
- (장점) 유연하다. 데이터 원소들을 차례로 방문할 때, 앞에서 뒤로도 할 수 있지만 뒤에서부터 앞으로도 할 수 있다.
✔️ 그 외 다중 연결 리스트 (Multiply linked list), 원형 연결 리스트 (Curcular linked list)
2. 스택 (Stacks)
"쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 (선형) 자료구조이며, 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출 구조(LIFO, Last In First Out)이다.
스택에 데이터 원소를 추가하는 (집어넣는) 동작을 푸시 (push) 연산이라고 하고, 마지막에 추가되었던 원소를 참조하고 삭제하는 (꺼내는) 동작을 팝 (pop) 연산이라고 한다. 스택은 이 두 연산을 제공하는 간단한 자료 구조인데, 여러 가지의 알고리즘을 구현하는 데 있어서 활용도가 높다.
예를 들어, 컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데에도 스택이 이용되고, 이러한 일은 컴퓨터의 동작에 핵심적인 것이기 때문에 컴퓨터 하드웨어 (프로세서) 는 어떤 방식으로든 스택을 내부적으로 관리하는 기능을 갖고 있다.
컴퓨터 내부에서뿐만 아니라, 응용 프로그램을 작성하는 데에도 스택을 활용하면 잘 풀어낼 수 있는 종류의 문제들이 많이 있다.
스택의 동작
초기 상태는 비어있는 스택 (empty stack)이다. Stack.push(Data) 형태를 통해서 데이터를 쌓을 수 있고, Stack.pop() 형태를 통해서 마지막에 넣은 데이터를 삭제할 수 있다.
그런데, 스택에서 2가지 오류가 발생할 수 있다.
➀ EmptyStack.pop() ⇨ 스택 언더플로우 (Stack underflow) : 비어있는 스택에서 원소를 꺼내려 할 때 발생하는 에러
➁ FullStack.push(data) ⇨ 스택 오버플로우 (Stack overflow) : 꽉 찬 스택에 원소를 넣으려 할 때 발생하는 에러
스택의 추상적 자료구조 구현
스택을 추상적 자료구조로 구현하고자 할 때는 대표적으로 두 가지 방법이 있다. (선형) 배열 구조를 이용하거나, 연결 리스트를 이용하는 방법이다. 이 외의 방법도 있지만 일단 이 두 가지만 먼저 살펴보기로 하자.
먼저, 이용하는 연산은 다음과 같다.
- size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
- isEmpty() : 현재 스택이 비어 있는지를 판단 (size() == 0?)
- push(x) : 데이터 원소 x 를 스택에 추가
- pop() : 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
- peek() : 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음
1) 배열 (Array)을 이용한 방법 : python 리스트와 메서드들을 이용
class AraayStack :
def __init__(self) :
# 빈 스택 초기화
self.data = []
def size(self) :
# 스택의 크기를 리턴
return len(self.data)
def isEmpty(self) :
# 스택이 비어있는지 판단 (T/F)
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) 연결 리스트를 이용한 방법 : 양방향 연결 리스트를 이용
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
이미 만들어진 파이썬 라이브러리를 이용해서 스택을 구현할 수도 있다.
from pythonds.basic.stack import Stack
3. 스택의 응용 - 수식의 후위 표기법 (Postfix Notation)
전위 표기법 (+AB) : 연산기호 뒤에 피연산자(연산수)를 표기
중위 표기법 (A+B) : 연산자를 두 피연산자(연산수) 사이에 표기 (기본)
후위 표기법 (AB+), 역폴란드표기법(reverse Polish notation) : 피연산자(연산수) 뒤에 연산기호를 표기
알고리즘 설계 :
- 수식을 왼쪽부터 한 글자씩 읽어서,
- 여는 괄호를 만나면 스택에 push
- 닫는 괄호를 만나면
- 스택이 비어 있으면 올바르지 않는 수식
- 쌍을 이루는 여는 괄호인지 검사
- 맞지 않으면 올바르지 않은 수식
- 여는 괄호를 만날 때까지 pop
- 끝까지 검사한 후, 스택이 비어 있어야 올바른 수식
중위 표기법 → 후위 표기법 변환 :
[중위] A * B + C → [하위] A B * C +
[중위] A + B * C → [하위] A B C * +
[중위] A + B + C → [하위] A B + C +
[중위] A * B + C → [하위] A B * C +
[중위] (A + B) * C → [하위] A B + C *
[중위] A * (B + C) → [하위] A B C + *
[중위] (A + B) * (C + D) → [하위] A B + C D + *
[중위] (A + (B - C)) * D → [하위] A B C - + D *
[중위] A * (B - (C + D)) → [하위] A B C D + - *
중위 표기법 → 후위 표기법 변환 알고리즘 구현 :
1. 연산자의 우선순위를 설정한다.
prec = {‘*’: 3, ‘/‘: 3, ‘+’ : 2, ‘-‘: 2, ‘(‘: 1}
⚠️ 연산자를 만났을 때, 여는 괄호 너머까지 pop 하지 않도록 여는 괄호의 우선순위를 가장 낮게 설정한다.
2. 중위 표현식을 왼쪽부터 한 글자씩 읽어서 행동한다.
피연산자 ➭ 그냥 출력
여는 괄호 ➭ 스택에 push
닫는 괄호 ➭ 여는 괄호가 나올 때까지 스택에서 pop하여 출력
연산자 ➭ 스택에서 높거나 같은 우선순위의 것들을 pop하여 출력, 그리고 이 연산자는 스택에 push
3. 스택에 남아 있는 연산자를 모두 pop하여 출력한다.
힌트!
➀ 스택의 맨 위에 있는 연산자와의 우선순위 비교 ➭ peek() 연산을 이용한다.
➁ 스택에 남아 있는 연산자 모두를 pop() 하는 순환문 ➭ while not Stack.isEmpty() 를 이용한다.
후위 표기법 수식 계산 알고리즘 구현 :
1. 후위 표현식을 왼쪽부터 한 글자씩 읽어서 행동한다.
`피연산자` ➭ 스택에 push
`연산자` ➭ 스택에 쌓인 2개의 피연산자들 pop하여 꺼낸 후, 해당 연산자를 적용한 결과값(`pop2값 연산자 pop1값`)을 스택에 push
2. 최종적으로 하나가 된 스택을 리턴한다.
📝 남아있는 의문과 개선점
아직 연결 리스트가 어렵다. 단일, 양방향 외에 다른 연결 리스트를 더 알아봐야겠다.
연결 리스트 실습을 풀지 못 했다.
후위 표기법 실습을 풀어야 한다.
☁️ 소감
새롭게 배우는 연결 리스트와 스택이 오늘의 내용이었다. 연결 리스트는 어려워서 더 공부를 해야 할 것 같다. 강사님은 쉽다고 얘기하시지만 초보자인 나의 입장에서는 낯설고 어려웠다. 다행히도 스택은 그보다는 쉬워서 이해하기 수월했고 재미있었다.
'Data Engineering > grepp 데브코스 : TIL' 카테고리의 다른 글
| [TIL_2023.10.20] 자료구조와 알고리즘 (5) : 힙, DFS/BFS, 동적 계획법 대표 문제 풀이 (1) | 2023.10.20 |
|---|---|
| [TIL_2023.10.19] 자료구조와 알고리즘 (4) : 해시 (Hash), 그리디 (Greedy)/탐욕법, 정렬 문제 (1) | 2023.10.19 |
| [TIL_2023.10.18] 자료구조와 알고리즘 (3) : 큐 Queues, 트리 Trees, 힙 Heaps (1) | 2023.10.18 |
| [TIL_2023.10.16] 자료구조와 알고리즘 (1) : 선형배열, 정렬/탐색, 재귀 알고리즘, 복잡도 (1) | 2023.10.16 |
| [TIL_2023.10.13] 오리엔테이션 (0) | 2023.10.13 |
