TIL 2일차
금주에는 기본적인 자료구조에 대해서 배운다.
데이터엔지니어링 관해서는 다음 주부터가 진짜 시작이지 않나 싶다.
연결리스트, 양방향 연결리스트, 스택, 후위표기식을 학습하고 실습을 진행했다.
추상적 자료구조(Abstract Data Structures)
내부 구현에 대해서 신경 쓸 필요가 없는 자료구조들
Data
- 정수, 문자열, 레코드
A set of operations
삽입, 삭제, 순회, ...
정렬, 탐색 ...
Linked list
Node
- Data
- link(next) 다음 원소
노드 내의 데이터는 다른 구조로 이루어질 수 있음 -> 리스트, 레코드
첫 노드는 Head
마지막 노드는 Tail
연산 정의
- 특정 원소 참조
- 리스트 순회
- 길이 얻어내기
- 원소 삽임
- 원소 삭제
- 두 리스트 합치기
특정 원소 참조
Head 같은 경우 index를 1로 시작한다. 0번은 다른 목적으로 이용하기 위해서.
배열과 비교한 연결 리스트
배열
저장공간 : 연속한 위치
특정 원소 지칭 : 매우 간편
O(1)
연결리스트
저장공간 : 임의의 위치
특정 원소 지칭 : 선형탐색과 유사
O(n) -> linear time algorithm
리스트 순회
문제)
class Node: #생성자
def __init__(self, item):
self.data = item
self.next = None 첫 노드이기에 next가 없음
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None #아무것도 가르키지 않음
self.tail = None #아무것도 가르키지 않음
#특정 원소 참조
def getAt(self, pos): # -> 주어진 위치
if pos < 1 or pos > self.nodeCount: # -> node count 같은 경우 총 노드의 개수
# 위 조건 같은 경우 주어진 위치가 1보다 작은지, 총 노드의 개수보다 인덱스가 큰지
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def traverse(self):
result = []
# 현재 노드를 헤드로 초기화합니다.
curr_node = self.head
# 현재 노드가 존재하는 동안 반복합니다.
while curr_node is not None:
# 현재 노드의 데이터를 결과 리스트에 추가합니다.
result.append(curr_node.data)
# 다음 노드로 이동합니다.
curr_node = curr_node.next
return result
# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
return 0Linked list - 원소의 삽입
insertAt으로 현 과정에서는 정의
내가 3번 인덱스에 넣고 싶다는 것은 2번 까지는 그대로 3번 이후로는 하나씩 밀림
ex) pos 번째에 넣고 싶다면
pos-1의 next node를 new node가 가리키 도록
pos-1 번째의 노드가 new node를 가르키도록
node count += 1
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:
# pos가 리스트의 마지막 원소 일때
if pos == self.nodeCount + 1:
prev = self.tail
else: #예외 조건 제외 일반적인 노드 삽입
prev = self.getAt(pos - 1)
newNode.next = prev.next
prev.next = newNode
# 만약 연결 리스트에 원소 하나라면 new node를 가리킴
# else 안의 같은 조건과 헷갈리면 안되는 것이, 만약 기존의 원소가 존재한다면
# nodecount가 pos + 1이 될 수 없음
if pos == self.nodeCount + 1:
self.tail = newNode
self.nodeCount += 1
return True연결 리스트 원소 삽입의 복잡도
맨 앞에 삽입하는 경우 : O(1)
중간에 삽입하는 경우 : O(n)
끝에 삽입하는 경우 : O(1) -> tail point를 가지고 있기에 상수시간
연결 리스트 연산 - 원소의 삭제
popAt(pos)로 구현
prev.next <- curr.next
nodeCount -= 1
삭제하려는 node가 맨 앞의 것일 때
-> prev 없음
-> Head 조정 필요
리스트 맨끝의 node tkrwp
-> tail 조정 필요
삭제하려는 노드가 마지막 노드일 때, 즉 pos == nodeCount인 경우
-> 삽입과 같이 한번에 처리할 수 없다. prev를 찾을 방법이 없으므로
그러므로) 맨 앞에 삽입하는 경우를 제외하고 길이에 비례하게 된다.
-> 그래서 이중 연결리스트를 사용한다
코드를 입력하세요연결 리스트 연산 - 두 리스트의 연결
concat(self,L)
원래의 tail의 next를 head로
tail은 연결할 리스트의 tail로
-> 뒤의 이어 붙는 인자 리스트가 빈 리스트라면 tail이 none이 되기 때문에
L.tail이 유효한 경우에만 붙일 수 있도록 조건
nodeCount 같은 경우는 두 리스트의 길이의 합
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
어디에 응용이 될까요?, 어디에서 힘을 발휘할 까요?
핸드폰의 백그라운드 같은 경우, 순서지어 연결되어 있을 때
삽입과 삭제가 유연하다는 것이 가장 큰 장점 -> 앞 뒤의 링크만 조절하면 된다.
하지만 삽입과 삭제시 필요한 모든 노드를 순서대로 확인해야 된다는 것이 있다.
새로운 method를 구현해보자
insertAfter(prev,newNode) -> pos를 알려주는 것이 아닌 노드를 알려주는 것
insertAt 같은 경우도 insertAfter를 이용해 보는 것으로 해보자
popAfter -> 동일
여기서 고려해야할 점 -> 맨 앞에서는 어떻게 진행할까
linked list를 확장해보자, 맨 앞에 dummyNode, pos=0 으로 구현해보자
양방향 연결 리스트(Doubly Linked Lists)
기존의 연결 리스트에서 Node 구조를 확장
prev를 none으로 생성
Stack
후입 선출
비어 있는 스택에서 데이터 원소를 꺼내려 할 때
-> stack underflow
꽉찬 스택에 데이터 원소를 넣으려 할 때
-> stack overflow
스택의 추상적 자료구조 구현
1. 배열 array을 이용하여 구현
size() - 현재 스택의 원소수
isEmpty() - 현재 스택이 비어 있는지 판단
push(x) - 데이터 원소 추가
pop() - 스택 맨위 저장된 데이터 원소 제거 반환
peek() - 스택의 맨 위에 저장된 원소 반환 (제거x)
2. 양뱡향 연결 리스트를 이용하여 구현
중위 표기법과 후위 표기법
중위 표기법 - 연산자가 피연산자들의 사이에 위치
(a+b) (c+d)
후위 표기법 - 연산자가 피연산자들의 뒤에 위치
AB+CD+
스택을 이용해서 중위 표현식을 후위 표현식으로 바꾸어 보자
